EXPERIMENT 2
AIM: To generate some random datasets. Thereafter, sort them using Merge and Quick sort and compare
the sorting time used by each algorithm.
THEORY:
1. Merge Sort: It is one of the most efficient sorting algorithms and follows the divide and conquer
approach. It divides the given array into two equal halves. It then sorts these two halves and merges
the then 2 sorted halves. The subarrays are divided repeatedly until they cannot be divided any
further. Then these subarrays are merged repeatedly- single element pairs combine to form 2
elements then 4 elements and so on until we get the sorted list.
Complexity: Time complexity: Always O(n*logn)
• Best case: This occurs when the array is already sorted.
• Average-case: This occurs when the array isn’t sorted and elements are in random order.
• Worst-case: Occurs when array has to be sorted in reverse order of its present one.
Space complexity: O(n) as an extra variable is required for swapping.
Algorithm:
i. merge_sort (arr[],beg,end)
ii. if beg <end
iii. set mid=(big+end)/2
iv. merge_sort(arr,beg,mid)
v. merge_sort(arr,mid+1,end)
vi. merge(arr,beg,mid,end)
vii. end of if
viii. end merge_sort
2. Quick Sort: This algorithm also follows the divide and conquer approach, and also a highly
efficient sorting algorithm. It picks up an element as pivot, then divides the array around that pivot
element. Then the array is divided into 2 subarrays- one which holds values larger than pivot element
and the other which holds values smaller than it. This repeated partitioning goes on until a single
element remains in the subarray.
Complexity: Time complexity:
• Best Case: O(n*logn)- Occurs when the pivot element is the middle one or near to it.
• Average Case: O(n*logn); occurs when elements are in random order.
• Worst Case- O(n2); occurs when pivot element is either the greatest or smallest. It would
occur when elements are already in ascending or descending order.
Space Complexity: O(n*logn)
Algorithm:
i. An element is chosen as the pivot
ii. 2 variables point to left and right of the array excluding the pivot element.
iii. Left points to low index
iv. Right points to higher
v. While value at left ≤ pivot, move right
vi. While value at right > pivot, move left
vii. If v and vi don’t match, swap left and right
viii. If right ≤ left, the point where they met is new pivot
PROGRAM CODE:
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <math.h>
#define LIMIT 500000
//creating files
char filename[5][15]={"numbers_1.dat","numbers_2.dat","numbers_3.dat","numbers_4.dat","numbers_5.dat"};
int partition(int a[],int lb, int ub)
int pivot=a[lb]; int temp;
int start=lb; int end=ub;
while(start<end)
while(a[start]<=pivot)
start++;
while(a[end]>pivot)
end--;
if(start < end) //Swap to re-arrange the Larger & Smaller Numbers
temp = a[start];
a[start] = a[end];
a[end] = temp;
}
// Swap to place the pivot at its right place
temp = a[lb];
a[lb] = a[end];
a[end] = temp;
return end; // Return the pivot position
void quick_sort(int a[], int lb, int ub)
if(lb< ub)
int pivot = partition(a, lb, ub);
quick_sort(a, lb, pivot-1);
quick_sort(a, pivot+1, ub);
void merge_sort(int a[],int lb, int ub)
int mid,i,j,k;
i=lb; j=mid+1;k=lb;
int b[LIMIT];
while(i<=mid && j<=ub)
if(a[i]<=a[j])
b[k]=a[i];
i++;
else
b[k]=a[j];
j++;
k++;
if (i>mid)
while(j<=ub)
b[k]=a[j];
j++; k++;
else
while(i<=mid)
b[k]=a[i];
i++;k++;
for (k=lb;k<=ub;k++)
a[k]=b[k];
int main()
struct timeval stop, start;
int i,a;
int random_number;
int arr[LIMIT];
FILE *file;
float diff[5];
float diff_merge[5];
float diff_quick[5];
//for loop for generating numbers, merge sort and quick sort for 5 files
for (a=0;a<5;a++)
//to generate random numbers- file is opened, srand is used as seed with reference to time(0)
//random numbers are generated using rand function
file=fopen(filename[a],"w");
srand((unsigned)time(0));
i=0;
do
random_number = (int) (rand()%1000) ;
fprintf(file, "%d\n", random_number);
i++;
}while (i<LIMIT);
fclose(file);
//quick sort
file=fopen(filename[a],"r");
i=0;
do
fscanf(file, "%d", &arr[i]);
i++;
}while (i<LIMIT);
fclose(file);
gettimeofday(&start, NULL);
quick_sort(arr, 0, LIMIT-1);
gettimeofday(&stop, NULL);
if(stop.tv_usec<start.tv_usec)
stop.tv_sec--;
stop.tv_usec+=1000000;
diff[a]=stop.tv_usec-start.tv_usec;
diff[a]=diff[a]/1000000.0;
//to calculate the time taken in sorting
diff_quick[a]=stop.tv_sec-start.tv_sec;
//printing the result of quick sort
printf("\n\nDATASET | quick SORT | merge SORT \n");
printf(" seconds seconds \n");
printf("-----------------------------------------------------------\n");
printf("%s\t\t%0.4f\t\t ",filename[a],diff_quick[a]+diff[a]);
//merge sort
file=fopen(filename[a],"r");
i=0;
do
fscanf(file, "%d", &arr[i]);
i++;
}while (i<LIMIT);
fclose(file);
gettimeofday(&start, NULL);
merge_sort (arr, 0, LIMIT-1);
gettimeofday(&stop, NULL);
if(stop.tv_usec<start.tv_usec)
stop.tv_sec--;
stop.tv_usec+=1000000;
}
diff[a]=stop.tv_usec-start.tv_usec;
diff[a]=diff[a]/1000000.0;
//to calculate the time taken in sorting
diff_merge[a]=stop.tv_sec-start.tv_sec;
//printing the result of merge sort
printf("%0.4f\n",diff_merge[a]+diff[a]);
printf("-----------------------------------------------------------\n");
return 0;
OUTPUT:
CONCLUSION:
We have learnt to use microseconds in calculation of time differences, also learnt to use merge and quick
sort for sorting of an array.
