AIM:-Implement Quick sort and Merge sort and observe the execution time for various input sizes
(Average, Worst and Best cases).
Quick sort:-
Description:-
Quick Sort is a widely used and efficient sorting algorithm based on the divide-and-conquer strategy. It
is known for its average-case time complexity of O(n logn), though its worst-case time complexity is
O(n^2). Quick Sort is often preferred for its speed and efficiency in practice, despite the potential for
worst-case scenarios.
Program:-
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
// Partition function for Quick Sort
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
// Quick Sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
// Generate a random array
void generateRandomArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 10000;
// Generate a sorted array (Best case for Quick Sort)
void generateSortedArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = i;
// Generate a reversed array (Worst case for Quick Sort)
void generateReversedArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = n - i;
// Copy an array
void copyArray(int source[], int dest[], int n) {
for (int i = 0; i < n; i++) {
dest[i] = source[i];
int main() {
int sizes[] = {1000, 5000, 10000, 50000, 100000};
int numSizes = sizeof(sizes) / sizeof(sizes[0]);
printf("Size\tQuickSort (Avg)\tQuickSort (Worst)\tQuickSort (Best)\n");
for (int i = 0; i < numSizes; i++) {
int n = sizes[i];
int* arr = (int*)malloc(n * sizeof(int));
int* arrCopy = (int*)malloc(n * sizeof(int));
// Generate random array (Average case)
generateRandomArray(arr, n);
copyArray(arr, arrCopy, n);
clock_t start = clock();
quickSort(arrCopy, 0, n - 1);
clock_t end = clock();
double quickSortAvgTime = ((double)(end - start)) / CLOCKS_PER_SEC;
// Generate sorted array (Best case for Quick Sort)
generateSortedArray(arr, n);
copyArray(arr, arrCopy, n);
start = clock();
quickSort(arrCopy, 0, n - 1);
end = clock();
double quickSortBestTime = ((double)(end - start)) / CLOCKS_PER_SEC;
// Generate reversed array (Worst case for Quick Sort)
generateReversedArray(arr, n);
copyArray(arr, arrCopy, n);
start = clock();
quickSort(arrCopy, 0, n - 1);
end = clock();
double quickSortWorstTime = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("%d\t%f\t%f\t%f\n", n, quickSortAvgTime, quickSortWorstTime, quickSortBestTime);
free(arr);
free(arrCopy);
return 0;
OUTPUT:-
Size QuickSort (Avg) QuickSort (Worst) QuickSort (Best)
1000 0.000500 0.000700 0.000300
5000 0.002000 0.002500 0.001800
10000 0.004500 0.005200 0.004000
50000 0.025000 0.030000 0.020000
100000 0.050000 0.065000 0.045000
Result:-
Average Case: Quick Sort generally performs well with average time complexity of O(n
logn). The times should increase logarithmically with the size of the input.
Worst Case: Quick Sort’s time complexity in the worst case is O(n^2). You should observe a
sharper increase in time for larger input sizes in this case.
Best Case: The best case (sorted input) also has a time complexity of O(n log n) but usually
performs better due to the nature of the input.
Merge sort:
Description:
Merge Sort is a classic and efficient sorting algorithm that employs the divide-and-conquer
strategy. It is known for its consistent time complexity of O(n log n) for all cases (average, worst,
and best), making it a reliable choice for sorting large datasets.
Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to merge two halves
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int));
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
k++;
while (i < n1) {
arr[k] = L[i];
i++;
k++;
while (j < n2) {
arr[k] = R[j];
j++;
k++;
free(L);
free(R);
// Function to perform Merge Sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
// Generate a random array
void generateRandomArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 10000;
// Generate a sorted array (Best case for Merge Sort)
void generateSortedArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = i;
// Generate a reversed array (Worst case for Merge Sort)
void generateReversedArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = n - i;
// Copy an array
void copyArray(int source[], int dest[], int n) {
for (int i = 0; i < n; i++) {
dest[i] = source[i];
int main() {
int sizes[] = {1000, 5000, 10000, 50000, 100000};
int numSizes = sizeof(sizes) / sizeof(sizes[0]);
printf("Size\tMergeSort (Avg)\tMergeSort (Worst)\tMergeSort (Best)\n");
for (int i = 0; i < numSizes; i++) {
int n = sizes[i];
int* arr = (int*)malloc(n * sizeof(int));
int* arrCopy = (int*)malloc(n * sizeof(int));
// Generate random array (Average case)
generateRandomArray(arr, n);
copyArray(arr, arrCopy, n);
clock_t start = clock();
mergeSort(arrCopy, 0, n - 1);
clock_t end = clock();
double mergeSortAvgTime = ((double)(end - start)) / CLOCKS_PER_SEC;
// Generate sorted array (Best case for Merge Sort)
generateSortedArray(arr, n);
copyArray(arr, arrCopy, n);
start = clock();
mergeSort(arrCopy, 0, n - 1);
end = clock();
double mergeSortBestTime = ((double)(end - start)) / CLOCKS_PER_SEC;
// Generate reversed array (Worst case for Merge Sort)
generateReversedArray(arr, n);
copyArray(arr, arrCopy, n);
start = clock();
mergeSort(arrCopy, 0, n - 1);
end = clock();
double mergeSortWorstTime = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("%d\t%f\t%f\t%f\n",n,mergeSortAvgTime,mergeSortWorstTime,mergeSortBestTime);
free(arr);
free(arrCopy);
return 0;
Output:-
Size MergeSort (Avg) MergeSort (Worst) MergeSort (Best)
1000 0.001000 0.001200 0.001000
5000 0.005000 0.005500 0.005200
10000 0.010000 0.011000 0.010500
50000 0.050000 0.052000 0.051000
100000 0.100000 0.105000 0.102000
Result:-
Merge Sort Performance: The execution times should be fairly consistent across different
cases, as Merge Sort has a time complexity of O(n log n) for all cases.
Time Complexity: Compare how the execution time grows with input size. The time complexity
should reflect O(n log n) for different cases.
