Assignment 2: Sorting Algorithms – Bubble Sort, Insertion Sort, Selection Sort
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.
Program
#include <stdio.h>
#define MAXSIZE 10
void main()
{
int array[MAXSIZE];
int i, j, num, temp;
printf("Enter the value of num \n");
scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array is \n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
for (i = 0; i < num; i++)
{
for (j = 0; j < (num - i - 1); j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
printf("Sorted array is...\n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
}
b) 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>
#define Max 100
int main(void)
{
int n,array[Max],i,j,temp;
printf("Enter the size of integer array: ");
scanf("%d", &n);
printf("\nEnter the elements of integer array: ");
for (i = 0; i < n; i++)
{
scanf("%d ", &array[i]);
}
for (i = 1 ; i <= n - 1; i++)
{
j = i;
while ( j > 0 && array[j-1] > array[j])
{
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
j--;
}
}
printf("\nSorted array in ascending order: ");
for (i = 0; i<= n - 1; i++)
{
printf("%d ", array[i]);
}
}
c) Sort a random array of n integers (accept the value of n from user) in ascending order by
using selection sort algorithm.
#include <stdio.h>
void selection_sort();
int a[30], n;
void main()
{
int i;
printf("\nEnter size of an array: ");
scanf("%d", &n);
printf("\nEnter elements of an array:\n");
for(i=0; i<n; i++)
scanf("%d", &a[i]);
selection_sort();
printf("\n\nAfter sorting:\n");
for(i=0; i<n; i++)
printf("\n%d", a[i]);
getch();
}
void selection_sort()
{
int i, j, min, temp;
for (i=0; i<n; i++)
{
min = i;
for (j=i+1; j<n; j++)
{
if (a[j] < a[min])
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
Set B
a) Read the data from the file “employee.txt” and sort on age using bubble sort, insertion sort and selection sort.
Program for Insertion sort :-
#include<stdio.h>
typedef struct employee
{
int age;
char name[10];
}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_on_age_emp.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 && a[j].age>t.age;j--)
{
a[j+1]=a[j];
a[j]=t;
}
}
}
Program for Bubble sort :-
main()
{
int n;
n=readfile(employee);
insertion(employee,n);
writefile(employee,n);
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct employee
{
int age;
};
void bubble(struct employee *emp,int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
struct employee temp;
if(emp[j].age <emp[j+1].age)
{
temp = emp[j+1];
emp[j+1]=emp[j];
emp[j]=temp;
}
}
}
}
void main()
{
struct employee *emp=NULL,temp;
FILE *fp;
int i,j,age,n;
fp=fopen("employee.txt","r");
while(fscanf(fp,"%d",&age)!=EOF)
n++;
emp=malloc(sizeof(struct employee)*n);
n=0;
rewind(fp);
while(fscanf(fp,"%d",&emp[n].age)!=EOF)
n++;
fclose(fp);
bubble(emp,n);
fp=fopen("employee.txt","w");
for(i=0;i<n;i++)
fprintf(fp,"%d\n",emp[i].age);
fclose(fp);
}
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.
Insert Sort
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct employee
{
char name[20];
};
void insertsort(struct employee emp[],int num)
{
struct employee temp;
int i,j;
for(i=1;i<num;i++)
{
temp=emp[i];
for(j=i-1;j>=0 && strcmp(emp[j].name,temp.name)>0;j--)
{
emp[j+1]=emp[j];
}
emp[j+1]=temp;
}
}
main()
{
struct employee *emp=NULL,temp;
FILE *fp;
int i,j,num;
char name[20];
fp=fopen("employee.txt","r");
while(fscanf(fp,"%s",name)!=EOF)
num++;
emp=malloc(sizeof(struct employee)*num);
num=0;
rewind(fp);
while(fscanf(fp,"%s",emp[num].name)!=EOF)
num++;
fclose(fp);
insertsort(emp,num);
fp=fopen("employee.txt","w");
for(i=0;i<num;i++)
fprintf(fp,"%s\n",emp[i].name);
fclose(fp);
}
Bubble Sort
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct employee
{
char name[20];
};
void bubble(struct employee *emp,int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
struct employee temp;
if(strcmp(emp[j].name, emp[j+1].name) > 0)
{
temp = emp[j+1];
emp[j+1]=emp[j];
emp[j]=temp;
}
}
}
}
void main()
{
struct employee *emp=NULL,temp;
FILE *fp;
int i,j,n;
char name[20];
fp=fopen("employeebb.txt","r");
while(fscanf(fp,"%s",name)!=EOF)
n++;
emp=malloc(sizeof(struct employee)*n);
n=0;
rewind(fp);
while(fscanf(fp,"%s",emp[n].name)!=EOF)
n++;
fclose(fp);
bubble(emp,n);
fp=fopen("employeebb.txt","w");
for(i=0;i<n;i++)
fprintf(fp,"%s\n",emp[i].name);
fclose(fp);
}
No comments:
Post a Comment