DSA -I 3: Sorting Algorithms –Counting Sort, Merge Sort, Quick Sort
Set A
a) Sort a random array of n integers (accept the value of n from user) in ascending order by using recursive Counting sort algorithm.
Program:-
#include<stdio.h>
int getMax(int a[], int n) {
int max = a[0];
for(int i = 1; i<n; i++) {
if(a[i] > max)
max = a[i];
}
return max; //maximum element from the array
}
void countSort(int a[], int n) // function to perform counting sort
{
int output[n+1];
int max = getMax(a, n);
int count[max+1]; //create count array with size [max+1]
for (int i = 0; i <= max; ++i)
{
count[i] = 0; // Initialize count array with all zeros
}
for (int i = 0; i < n; i++) // Store the count of each element
{
count[a[i]]++;
}
for(int i = 1; i<=max; i++)
count[i] += count[i-1]; //find cumulative frequency
/* This loop will find the index of each element of the original array in count array, and
place the elements in output array*/
for (int i = n - 1; i >= 0; i--) {
output[count[a[i]] - 1] = a[i];
count[a[i]]--; // decrease count for same numbers
}
for(int i = 0; i<n; i++) {
a[i] = output[i]; //store the sorted elements into main array
}
}
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main() {
int a[] = { 11, 30, 24, 7, 31, 16 };
int n = sizeof(a)/sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
countSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
b)Sort a random array of n integers (accept the value of n from user) in ascending order by using a recursive Merge sort algorithm.
Program:-
#include<stdio.h>
#include<stdlib.h>
void display(int num[10],int n);
void generate(int num[10],int n);
void mergesort(int a[10],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int num[10],n;
printf("Enter how many numbers: ");
scanf("%d",&n);
generate(num,n);
printf("These are random numbers generated: ");
display(num,n);
printf("\n");
mergesort(num,0,n-1);
printf("\nAfter sorting: ");
display(num,n);
return 0;
}
void generate(int num[10],int n)
{
int i;
for(i=0;i<n;i++)
num[i]=rand()%100;
}
void display(int num[10],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",num[i]);
}
void mergesort(int a[],int i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid);
mergesort(a,mid+1,j);
merge(a,i,mid,mid+1,j);
}
}
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50];
int i,j,k;
i=i1;
j=i2;
k=0;
while(i<=j1 && j<=j2)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1)
temp[k++]=a[i++];
while(j<=j2)
temp[k++]=a[j++];
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}
c) Sort a random array of n integers (create a random array of n integers) in ascending order by using recursive Quick sort algorithm.
Program:-
#include<stdio.h>
void display(int num[10],int n);
void generate(int num[10],int n);
void qsort(int arr[10],int low,int high);
int main()
{
int num[10],n;
printf("Enter how many numbers: ");
scanf("%d",&n);
generate(num,n);
printf("These are random numbers generated: ");
display(num,n);
printf("\n");
qsort(num,0,n-1);
printf("\nAfter sorting: ");
display(num,n);
return 0;
}
void generate(int num[10],int n)
{
int i;
for(i=0;i<n;i++)
num[i]=rand()%100;
}
void display(int num[10],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",num[i]);
}
void qsort(int arr[10],int low,int high)
{
int pivot,i,j,temp;
if(low<high)
{
pivot=low;
i=low+1;
j=high;
while(i<=j)
{
while(arr[i]<=arr[pivot] && i<=high)
i++;
while(arr[j]>arr[pivot] && j>=low)
j--;
if(i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}//if
}//while
temp=arr[j];
arr[j]=arr[pivot];
arr[pivot]=temp;
qsort(arr,low,j-1);
qsort(arr,j+1,high);
}//if
}//qsort
Set B
a)Read the data from the ‘employee.txt’ file and sort on age using Counting sort, Merge sort, Quick sort and write the sorted data to another file 'sortedemponage.txt'.
Program for Quick Sort :-
#include <stdio.h>
#include <stdlib.h>
struct employee
{
int age;
};
int cntRec(char fnm[])
{
int n=0,age;
FILE *fp;
fp = fopen(fnm,"r");
while( fscanf(fp,"%d",&age) != EOF )
n++;
fclose(fp);
return n;
}
void Quick_Sort(struct employee *emp,int lb,int ub)
{
if( lb < ub )
{
int p;
p = Partition(emp, lb, ub);
Quick_Sort(emp, lb, p-1);
Quick_Sort(emp, p+1, ub);
}
}
void sort(struct employee *emp, int n)
{
Quick_Sort(emp,0,n-1);
}
int Partition(struct employee *emp, int lb, int ub)
{
struct employee temp = emp[lb];
int down, up;
down = lb;
up = ub;
while( down < up )
{
while( down <= ub && emp[down].age <= temp.age ) down++;
while( emp[up].age > temp.age ) up--;
if( down < up )
{
struct employee t = emp[down];
emp[down] = emp[up];
emp[up] = t;
}
}
emp[lb] = emp[up];
emp[up] = temp;
return up;
}
void fetchRec(struct employee *emp, char fnm[])
{
FILE *fp;
int i=0;
fp = fopen(fnm,"r");
while( fscanf(fp,"%d",&emp[i].age) != EOF )
i++;
fclose(fp);
}
updateFile(struct employee *emp, int n, char fnm[])
{
int i;
FILE *fp;
fp = fopen(fnm,"w");
for(i=0; i<n; i++)
fprintf(fp,"%d\n",emp[i].age);
fclose(fp);
}
main()
{
int n=0;
struct employee *emp;
n = cntRec("employee.txt");
emp = malloc(sizeof(struct employee) * n );
fetchRec(emp,"employee.txt");
sort(emp,n);
updateFile(emp,n,"sortedemponage.txt");
}
Program for Merge Sort :-
#include<stdio.h>
typedef struct employee
{
char name[10];
int age;
}record;
record employee[100];
int readfile(record *a)
{
int i=0;
FILE *fp;
if((fp=fopen("emp.txt","r"))!=NULL)
{while(!feof(fp))
{
fscanf(fp,"%d%s",&a[i].age,a[i].name);
i++;
}}
return(i-1);
}
void writefile(record *a,int n)
{
int i=0;
FILE *fp;
if((fp=fopen("sorted_emp_on_age_merge.txt","w"))!=NULL)
{
for(i=0;i<n;i++)
fprintf(fp,"%d%s\n",a[i].age,a[i].name);
}}
merge(record *a,int l,int m,int u)
{
record c[10]; int i,j,k;
i=l;
j=m+1;
k=0;
while(i<=m && j<=u)
{
if(a[i].age<a[j].age)
{
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];
}
merge_sort(record *a,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 n;
n=readfile(employee);
merge_sort(employee,0,n-1);
writefile(employee,n);
}
b)Read the data from the file and sort on names in alphabetical order (use strcmp) using Counting sort, Merge sort, Quick sort and write the sorted data to another file 'sortedemponname.txt'.
Coming Soon...........
No comments:
Post a Comment