ASSIGNMENT-2 [SORTED

ALGORITHMS]
SET A)

A) Sort a random array of n integers (accept the value of n from user) in ascending
order by using bubble sort algorithm.
#include<stdio.h>
void bubble(int a[20],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

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

{
int i;
for(i=0;i<n;i++)
a[i]=rand()%1000;
}

void display(int a[],int n)

{ int i;
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
main()
{
int a[20],i,j,n;
printf("\nenter how many elemants:");
scanf("%d",&n);
generate(a,n);
printf("\n elements are:\n");
display(a,n);
bubble(a,n);
printf("\n after sorting elements are :\n");
display(a,n);
}
OUTPUT: enter how many elemants:5
elements are:
383 886 777 915 793
after sorting elements are :
383 777 793 886 915

a) Sort a random array of n integers (create a random array of n integers) in

ascending order by using insertion sort algorithm.
#include<stdio.h>

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

{
int i,j,key;
for(i=1;i<n;i++)
{
key=a[i];
for(j=i-1;j>=0 ;j--)
{
if(key<a[j])
a[j+1]=a[j]; //shifting
else break;
}
a[j+1]=key;
}
}

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

{
int i;
for(i=0;i<n;i++)
a[i]=rand()%2000;
}

void display(int a[],int n)

{ int i;
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}

main()
{
int a[20],i,j,n;
printf("\n Enter how many elemants:");
scanf("%d",&n);
generate(a,n);
printf("\n Elements are:\n");
display(a,n);
insertion(a,n);
printf("\n After sorting elements are :\n");
display(a,n);
}
OUTPUT: Enter how many elemants:3
Elements are:
1383 886 777
After sorting elements are :
777 886 1383

b) Sort a random array of n integers (accept the value of n from user) in ascending
order by using selection sort algorithm.

// Selection sort in C

#include <stdio.h>

// function to swap the the position of two elements

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void selectionSort(int array[], int size) {

for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {

// To sort in descending order, change > to < in this line.

// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}

// put min at the correct position

swap(&array[min_idx], &array[step]);
}
}

// function to print an array

void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}

// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}

SET B)
a) Read the data from the file “employee.txt” and sort on age using bubble sort,
insertion sort and selection sort.
>>BUBBLE SORT
#include<stdio.h>
typedef struct record
{
char name[30];
int age;
}record;

int fileread(record a[20])

{
FILE *fp;
int i=0;

fp=fopen("employee.txt","r");
if(fp==NULL)
printf("File Not Exist");
else
{
while(!feof(fp))
{
fscanf(fp,"%s%d", a[i].name, &a[i].age);
i++;
}
fclose(fp);
}
return i-1;
}

//Main
int main()
{
int i, n;

record a[20];
n = fileread(a);

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

printf("%s %d\n", a[i].name, a[i].age);
/* displaying records*/

bubblesort(n);
}
void bubblesort(int n)
{
record a[20],b[30];
n=fileread(a);
int i,j,temp,k;
char str[20];
for(i=0; i<n; i++)
{
for(j=0; j<n-i-1; j++)
{
if(a[j].age>a[j+1].age)
{
for(k=0;k<='\0';k++)
b[k]=a[j];
a[j]=a[j+1];
for(k=0;k<='\0';k++)
a[j+1]=b[k];

}
}
}
printf("Sorted list:\n");
for(int i=0; i<n; i++)
printf("%s %d\n", a[i].name, a[i].age);

>>INSERTION SORT
#include<stdio.h>

typedef struct record

{
char name[30];
int age;
}record;

int fileread(record a[20])

{
FILE *fp;
int i=0;

fp=fopen("employee.txt","r");
if(fp==NULL)
printf("File Not Exist");
else
{
while(!feof(fp))
{
fscanf(fp,"%s%d", a[i].name, &a[i].age);
i++;
}
fclose(fp);
}
return i-1;
}

//Main
int main()
{
int i, n;
char key[20];
record a[20];
n = fileread(a);

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

printf("%s %d\n", a[i].name, a[i].age);
/* displaying records*/

insertion_sort(n);
}
void insertion_sort(int n)
{
record a[20],b[30];
n=fileread(a);
int temp,i,j,k;
for (i=0 ;i<n ;i++)
{
temp= a[i].age;
for(k=0;k<='\0';k++)
b[k]=a[i];
j = i - 1;
while (temp<a[j].age && j>=0)
{
a[j + 1].age = a[j].age;
for(k=0;k<='\0';k++)
a[j+1]=a[j];
j = j - 1;
}
for(k=0;k<='\0';k++)
a[j+1]=b[k];
a[j + 1].age = temp;

}
printf("Sorted list:\n");
for(int i=0; i<n; i++)
printf("%s %d\n", a[i].name, a[i].age);
}

>>SELECTION SORT
#include<stdio.h>

typedef struct record

{
char name[30];
int age;
}record;

int fileread(record a[20])

{
FILE *fp;
int i=0;

fp=fopen("employee.txt","r");
if(fp==NULL)
printf("File Not Exist");
else
{
while(!feof(fp))
{
fscanf(fp,"%s%d", a[i].name, &a[i].age);
i++;
}
fclose(fp);
}
return i-1;
}

//Main
int main()
{
int i, n;

record a[20];
n = fileread(a);

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

printf("%s %d\n", a[i].name, a[i].age);
/* displaying records*/

selection_sort(n);
}
void selection_sort(int n)
{
record a[20],b[30];
n=fileread(a);
int i,j,k,min;
for(i=0;i<n;i++)
{
min = i;
for(j=i+1;j<n;j++)
{
if(a[j].age<a[min].age)
min = j;
}
for(k=0;k<='\0';k++)
b[k]=a[i];
a[i]=a[min];
for(k=0;k<='\0';k++)
a[min]=b[k];
}
printf("Sorted list:\n");
for(int i=0; i<n; i++)
printf("%s %d\n", a[i].name, a[i].age);
}
b) Read the data from the file “employee.txt” and sort on names in alphabetical order
(use strcmp) using bubble sort, insertion sort and selection sort.
>>BUBBLE 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_name_bubble.txt","w+"))!=NULL)
{
for(i=0;i<n;i++)
fprintf(fp,"%d%s\n",a[i].age,a[i].name);
}

}
void bubble_sort(record *a,int n)
{
int i,j; record t;
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(strcmp(a[j].name,a[j+1].name)>=0)
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}

main()
{
int n;
n=readfile(employee);
bubble_sort(employee,n);
writefile(employee,n);
}

>>INSERTION SORT
#include<stdio.h>
typedef struct employee
{
int age; char name[10];
}record;

record employee[50];

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;
FILE *fp;
if((fp=fopen("sorted_on_name_insertion.txt","w"))!=NULL)
{
for(i=0;i<n;i++)
{
fprintf(fp,"%d%s\n",a[i].age,a[i].name);
}
}
}

void insertion(record *a,int n)

{
int i,j;
record t;
for(i=1;i<n;i++)
{
t=a[i];
for(j=i-1;j>=0 && (strcmp(a[j].name,t.name)>=0);j--)
{
a[j+1]=a[j];
a[j]=t;
}
}
}

main()
{
int n;
n=readfile(employee);
insertion(employee,n);
writefile(employee,n);
}

>>SELECTION SORT
-----------------------------

Assignment 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
#include <stdio.h>
int main()
{
int n, array[1000], c, d, t;

printf("Enter number of elements\n");

scanf("%d", &n);

printf("Enter %d integers\n", n);

for (c = 0; c < n; c++) {

scanf("%d", &array[c]);
}

for (c = 1 ; c <= n - 1; c++) {

d = c;

while ( d > 0 && array[d-1] > array[d]) {

t = array[d];
array[d] = array[d-1];
array[d-1] = t;

d--;
}
}
printf("Sorted list in ascending order:\n");

for (c = 0; c <= n - 1; c++) {

printf("%d\n", array[c]);
}

return 0;
}

Output:
Enter number of elements
5
Enter 5 integers
5
7
9
3
6
Sorted list in ascending order:
3
5
6
7
9

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
#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]);
}

b) Sort a random array of n integers (create a random array of n

integers) in ascending order by using recursive Quick sort algorithm
#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, Merge sort, Quick sort and write the sorted data to
another file 'sortedemponage.txt'.
>>COUNTING SORT
---------------------------
>>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);
}

>>QUICK SORT
#include<stdio.h>
enum bool {false,true};

typedef struct employee

{
int age; char name[10];
}record;
record employee[50];

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;
FILE *fp;
if((fp=fopen("sorted_on_age_quick.txt","w"))!=NULL)
{
for(i=0;i<n;i++)
{
fprintf(fp,"%d%s\n",a[i].age,a[i].name);
}
}
}
//enum bool {false,true};
void quick(record *a,int l,int u)
{
record temp;int 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].age<=a[right].age && piv!=right)
right--;
if(piv==right)
pivot_places=true;
if(a[piv].age>a[right].age)
{
temp=a[piv];
a[piv]=a[right];
a[right]=temp;
piv=right;
}
while(a[piv].age>=a[left].age && piv!=left)
left++;
if(piv==left)
pivot_places=true;
if(a[piv].age<a[left].age)
{
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);
}

main()
{
int n;
n=readfile(employee);
quick(employee,0,n-1);
writefile(employee,n);
}