Write a program to sort a given set of elements using the Merge sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted, and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.
Program
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
int b[r]; //same size of a[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(a[i] < a[j])
{
b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}
while(i <= q)
{
b[k++] = a[i++];
}
while(j <= r)
{
b[k++] = a[j++];
}
for(i=r; i >= p; i--)
{
a[i] = b[--k]; // copying back the sorted list to a[]
}
}
void mergeSort(int a[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
}
// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int k;
int inputs[] = {5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000,
45000, 50000} ;
time_t start, end;
double t;
printf("enter the size of array:");
scanf("%d",&k);
int brr[k];
printf("\n");
for(int i = 0; i<k; i++)
{
brr[i]=1+rand()%100;
}
printf("array elements:\n");
printArray(brr, k);
printf("\n");
mergeSort(brr,0,k-1);
printf("sorted array:\n");
printArray(brr, k);
printf("\n");
printf("\n");
printf("for differnt values of n :\n");
printf("n\t\tTime taken\n");
for(int j=0;j<10;j++)
{
int n = inputs[j];
int arr[n];
for(int i = 0; i<n; i++)
{
arr[i]=1+rand()%n;
}
start = clock();
mergeSort(arr,0,n-1);
end = clock();
t = (end - start) * 1.0 / CLOCKS_PER_SEC;
printf("%d\t\t ",n);
printf("%f\n", t);
}
return 0;
}
Output
enter the size of array:10
array elements:
84 87 78 16 94 36 87 93 50 22
sorted array:
16 22 36 50 78 84 87 87 93 94
for differnt values of n :
n Time taken
5000 0.001222
10000 0.002617
15000 0.004088
20000 0.005574
25000 0.007154
30000 0.008485
35000 0.009948
40000 0.011601
45000 0.012895
50000 0.013872
Tags:
DAA