NEP-SYBCS- DS-I Assignment- 3

 Assignment 3 Sorting Algorithms –Counting Sort, Merge Sort, Quick Sort

Set A

a) Accept the array of n integers from user and sort the array in ascending order by using

recursive Counting sort algorithm.

/*

 * C Program for counting sort

 */

#include <stdio.h>  

 

void counting_sort(int A[], int k, int n)

{

    int i, j;

    int B[15], C[100];

    for (i = 0; i <= k; i++)

        C[i] = 0;

    for (j = 1; j <= n; j++)

        C[A[j]] = C[A[j]] + 1;

    for (i = 1; i <= k; i++)

        C[i] = C[i] + C[i-1];

    for (j = n; j >= 1; j--)

    {

        B[C[A[j]]] = A[j];

        C[A[j]] = C[A[j]] - 1;

    }

    printf("The Sorted array is : ");

    for (i = 1; i <= n; i++)

        printf("%d ", B[i]);

}

int main()

{

    int n, k = 0, A[15], i;

    printf("Enter the number of input : ");

    scanf("%d", &n);

    printf("\nEnter the elements to be sorted :\n");

    for (i = 1; i <= n; i++)

    {

        scanf("%d", &A[i]);

        if (A[i] > k) {

            k = A[i];

        }

    }

    counting_sort(A, k, n);

    printf("\n");

    return 0;

}

b) Create random array of n integers and sort the array in ascending order by using recursive

Merge sort algorithm

Program

#include<stdio.h>

merge(int a[10],int l,int m,int u)

{

                int c[10],i,j,k;

                i=l;

                j=m+1;

                k=0;

                while(i<=m && j<=u)

                {

                                if(a[i]<a[j])

                                {

                                                c[k]=a[i];

                                                k++;i++;

                                }

                                else

                                {

                                                c[k]=a[j];

                                                k++;j++;

                                }

                }

                while(i<=m)

                {

                                c[k]=a[i];

                                i++;k++;

                }

                while(j<=u)

                {

                                c[k]=a[j];

                                k++;j++;

                }

                for(i=l,j=0;i<=u;i++,j++)

                                a[i]=c[j];

}

void generate(int a[10],int n)

{

                int i;

                for(i=0;i<n;i++)

                                a[i]=rand()%10;

}

merge_sort(int a[10],int i,int j)

{

                int k=0;

                if(i<j)

                {

                                k=(i+j)/2;

                                merge_sort(a,i,k);

                                merge_sort(a,k+1,j);

                                merge(a,i,k,j);

                }

}

main()

{

                int i,n,a[10];

                printf("how many elements:");

                scanf("%d",&n);

                generate(a,n);

                printf("elements are:\n");

                for(i=0;i<n;i++)

                                printf("%d\t",a[i]);

                merge_sort(a,0,n-1);

                printf("\nafter sorting:\n");

                for(i=0;i<n;i++)

                printf("%d\t",a[i]);

}

c) Accept the array of n integers from user and sort the array in ascending order by using

recursive Quick sort algorithm.

Program

#include<stdio.h>

enum bool {false,true};

void disp(int a[],int l,int u)

{

                int i;

                for(i=l;i<=u;i++)

                                printf("%d\t",a[i]);

}

void quick(int a[],int l,int u)

{

                int temp,piv,left,right;

                enum bool pivot_places=false;

                left=l;

                right=u;

                piv=l;

                if(l>=u)

                                return;

                printf("\nsublist:\n");

                disp(a,l,u);

                while(pivot_places==false)

                {

                                while(a[piv]<=a[right] && piv!=right)

                                                right--;

                                if(piv==right)

                                                pivot_places=true;

                                if(a[piv]>a[right])

                                {

                                                temp=a[piv];

                                                a[piv]=a[right];

                                                a[right]=temp;

                                                piv=right;

                                }

                                while(a[piv]>=a[left] && piv!=left)

                                                left++;

                                if(piv==left)

                                                pivot_places=true;

                                if(a[piv]<a[left])

                                {

                                                temp=a[piv];

                                                a[piv]=a[left];

                                                a[left]=temp;

                                                piv=left;

                                }

                }

                disp(a,l,u);

                quick(a,l,piv-1);

                quick(a,piv+1,u);

}

void generate(int a[],int n)

{

                int i;

                for(i=0;i<n;i++)

                                a[i]=rand()%20;

}

main()

{

                int a[10],n,i;

                printf("how many elements:");

                scanf("%d",&n);

                generate(a,n);

                printf("\nelements are:");

                for(i=0;i<n;i++)

                                printf("%d\t",a[i]);

                quick(a,0,n-1);

                printf("\nafter sorting:\n");

                for(i=0;i<n;i++)

                                printf("%d\t",a[i]);

}

Set B

a) Read the data from the ‘employee.txt’ file and sort on age using Counting sort and Merge

sort. Write the sorted data to another file 'sortedemponage.txt'.

employee.txt (Input File)

Amit 25 30000
Neha 22 35000
Rahul 30 45000
Priya 24 40000
Karan 28 38000

(Format: Emp_name Age Salary)

1. Counting Sort on Age

#include <stdio.h>

#include <string.h>

struct Employee

{

    char name[30];

    int age;

    float salary;

};

int main()

{

    struct Employee emp[100], output[100];

    int count[101] = {0};

    int n = 0, i;

    FILE *fp, *fs;

    fp = fopen("employee.txt", "r");

    if (fp == NULL)

    {

        printf("File not found.\n");

        return 1;

    }

    while (fscanf(fp, "%s%d%f",

                  emp[n].name,

                  &emp[n].age,

                  &emp[n].salary) != EOF)

    {

        n++;

    }

    fclose(fp);

    // Count frequency of ages

    for (i = 0; i < n; i++)

        count[emp[i].age]++;

    // Cumulative count

    for (i = 1; i <= 100; i++)

        count[i] += count[i - 1];

    // Build output array

    for (i = n - 1; i >= 0; i--)

    {

        output[count[emp[i].age] - 1] = emp[i];

        count[emp[i].age]--;

    }

    fs = fopen("sortedemponage.txt", "w");

    fprintf(fs, "Name\tAge\tSalary\n");

    for (i = 0; i < n; i++)

        fprintf(fs, "%s\t%d\t%.2f\n",

                output[i].name,

                output[i].age,

                output[i].salary);

    fclose(fs);

    printf("Data sorted using Counting Sort.\n");

    return 0;

}

2. Merge Sort on Age

#include <stdio.h>

#include <string.h>

struct Employee

{

    char name[30];

    int age;

    float salary;

};

void merge(struct Employee a[], int low, int mid, int high)

{

    struct Employee temp[100];

    int i = low, j = mid + 1, k = low;

    while (i <= mid && j <= high)

    {

        if (a[i].age <= a[j].age)

            temp[k++] = a[i++];

        else

            temp[k++] = a[j++];

    }

    while (i <= mid)

        temp[k++] = a[i++];

    while (j <= high)

        temp[k++] = a[j++];

    for (i = low; i <= high; i++)

        a[i] = temp[i];

}

void mergeSort(struct Employee a[], int low, int high)

{

    if (low < high)

    {

        int mid = (low + high) / 2;

        mergeSort(a, low, mid);

        mergeSort(a, mid + 1, high);

        merge(a, low, mid, high);

    }

}

int main()

{

    struct Employee emp[100];

    int n = 0, i;

    FILE *fp, *fs;

    fp = fopen("employee.txt", "r");

    if (fp == NULL)

    {

        printf("File not found.\n");

        return 1;

    }

    while (fscanf(fp, "%s%d%f",

                  emp[n].name,

                  &emp[n].age,

                  &emp[n].salary) != EOF)

    {

        n++;

    }

    fclose(fp);

    mergeSort(emp, 0, n - 1);

    fs = fopen("sortedemponage.txt", "w");

    fprintf(fs, "Name\tAge\tSalary\n");

    for (i = 0; i < n; i++)

        fprintf(fs, "%s\t%d\t%.2f\n",

                emp[i].name,

                emp[i].age,

                emp[i].salary);

    fclose(fs);

    printf("Data sorted using Merge Sort.\n");

    return 0;

}

b) Read the data from the file and sort on names in alphabetical order (use strcmp) using Quick

sort and write the sorted data to another file 'sortedemponname.txt'.

employee.txt (Input File)

Amit 25 30000
Neha 22 35000
Rahul 30 45000
Priya 24 40000
Karan 28 38000

Format: Emp_name Age Salary




C Program (Quick Sort on Employee Name)

#include <stdio.h>
#include <string.h>

struct Employee
{
    char name[30];
    int age;
    float salary;
};

void quickSort(struct Employee emp[], int low, int high);
int partition(struct Employee emp[], int low, int high);

int main()
{
    struct Employee emp[100];
    int n = 0, i;
    FILE *fp, *fs;

    fp = fopen("employee.txt", "r");

    if (fp == NULL)
    {
        printf("File not found.\n");
        return 1;
    }

    while (fscanf(fp, "%s%d%f",
                  emp[n].name,
                  &emp[n].age,
                  &emp[n].salary) != EOF)
    {
        n++;
    }

    fclose(fp);

    quickSort(emp, 0, n - 1);

    fs = fopen("sortedemponname.txt", "w");

    if (fs == NULL)
    {
        printf("Cannot create output file.\n");
        return 1;
    }

    fprintf(fs, "Name\tAge\tSalary\n");

    for (i = 0; i < n; i++)
    {
        fprintf(fs, "%s\t%d\t%.2f\n",
                emp[i].name,
                emp[i].age,
                emp[i].salary);
    }

    fclose(fs);

    printf("Data sorted successfully using Quick Sort.\n");
    printf("Sorted data stored in sortedemponname.txt\n");

    return 0;
}

int partition(struct Employee emp[], int low, int high)
{
    struct Employee pivot = emp[high], temp;
    int i = low - 1, j;

    for (j = low; j < high; j++)
    {
        if (strcmp(emp[j].name, pivot.name) < 0)
        {
            i++;
            temp = emp[i];
            emp[i] = emp[j];
            emp[j] = temp;
        }
    }

    temp = emp[i + 1];
    emp[i + 1] = emp[high];
    emp[high] = temp;

    return i + 1;
}

void quickSort(struct Employee emp[], int low, int high)
{
    if (low < high)
    {
        int p = partition(emp, low, high);
        quickSort(emp, low, p - 1);
        quickSort(emp, p + 1, high);
    }
}