Your task is to 1. Sort the first ‘N’ numbers in this file using “Merge Sort”, “
ID: 3801778 • Letter: Y
Question
Your task is to
1. Sort the first ‘N’ numbers in this file using “Merge Sort”, “Insertion Sort”, “Selection Sort” algorithms,
2. Measure their running time for N = 100 ~ 1,000,000 and
3. Plot a graph that compares the running time of the two algorithms.
You must implement using C, and you must implement two separate programs, “merge_sort.c”, “insertion_sort.c”, and “selection_sort.c”. The file names must be exactly as given, otherwise it won’t be graded and you will get zero points.
Your program must take two command line arguments: <input filename> and <N>
Ex> ./<your_program> <input_file> <N>
Ex> ./merge_sort hw1_input.txt 1000
Ex> ./insertion_sort hw1_input.txt 10000
Ex> ./selection_sort hw1_input.txt 100000
Your program should do the following
For a given N value, read the first N integers from the input file, put them into an array of integers, and sort them using each sorting algorithm.
o if N > K, then your program should sort all K numbers in the file correctly.
Your program must output the sorted result as well as the running time of the program in milliseconds.
To measure running time,
You may use the 'gettimeofday()' function or the 'clock()' function in your C program.
Please be careful about measuring time for small N values; the time will be very small, you need to think carefully about how to measure that small amount of time.
Explanation / Answer
/*Program to sort elements of an array using insertion sort method*/
#include<stdio.h>
#include<conio.h>
void main( )
{
int a[10],i,j,k,n;
clrscr( );
printf("How many elements you want to sort? ");
scanf("%d",&n);
printf(" Enter the Elements into an array: ");
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
k=a[i];
for(j= i-1; j>=0 && k<a[j]; j--)
a[j+1]=a[j];
a[j+1]=k;
} printf(" Elements after sorting: ");
for(i=0;i<n;i++)
printf("%d ", a[i]);
getch( );
}
OUTPUT:
How many elements you want to sort ? : 6
Enter elements for an array : 78 23 45 8 32 36
After Sorting the elements are : 8 23 32 36 45 78
/* program to sort elements of an array using selection sort*/
#include<stdio.h>
void main( )
{
int i,j,t,n,min,a[10];
clrscr( );
printf(" How many elements you want to sort? ");
scanf("%d",&n);
printf("Enter elements for an array:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
min=i;
for(j=i+1;j<n;j++)
if(a[j] > a[min])
{
min=j;
}
t=a[i];
a[i]=a[min];
a[min]=t;
} printf(" After sorting the elements are:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch( );
}
OUTPUT
How many elements you want to sort? : 5
Enter elements for an array : 2 6 4 8 5
After Sorting the elements are : 8 6 5 4 2
/* program to sort elements of an array using Merge Sort */
#include<stdio.h>
void disp( );
void mergesort(int,int,int);
void msortdiv(int,int);
int a[50],n;
void main( )
{
int i;
clrscr( );
printf(" Enter the n value:");
scanf("%d",&n);
printf(" Enter elements for an array:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf(" Before Sorting the elements are:");
disp( );
msortdiv(0,n-1);
printf(" After Sorting the elements are:");
disp( );
getch( );
}
void disp( )
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
void mergesort(int low,int mid,int high)
{
int t[50],i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid) && (j<=high))
{
if(a[i]>=a[j])
t[k++]=a[j++];
else
t[k++]=a[i++];
}
while(i<=mid)
t[k++]=a[i++];
while(j<=high)
t[k++]=a[j++];
for(i=low;i<=high;i++)
a[i]=t[i];
}
void msortdiv(int low,int high)
{
int mid;
if(low!=high)
{
mid=((low+high)/2);
msortdiv(low,mid);
msortdiv(mid+1,high);
mergesort(low,mid,high);
}
}
OUTPUT:
How many elements you want to sort ? : 7
Enter elements for an array : 88 45 54 8 32 6 12
After Sorting the elements are : 6 8 12 32 45 54 88
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.