Design and implement C/C++ Program to sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. 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.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Swap utility function
void swap(long int* a, long int* b) {
long int tmp = *a;
*a = *b;
*b = tmp;
}
// Partition function to partition the array and return the pivot index
long int partition(long int arr[], long int low, long int high) {
long int pivot = arr[high]; // Choose the last element as pivot
long int i = low - 1; // Index of smaller element
for (long int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Quick sort function
void quickSort(long int arr[], long int low, long int high) {
if (low < high) {
// Partitioning index
long int pi = partition(arr, low, high);
// Separately sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Driver code
int main() {
long int n = 10000;
int it = 0;
// Arrays to store time duration of sorting algorithms
double time[10];
printf("A_size, Quick\n");
// Perform 10 iterations
while (it++ < 10) {
long int a[n];
// Generating n random numbers and storing them in arrays a
for (int i = 0; i < n; i++) {
long int num = rand() % n + 1;
a[i] = num;
}
// Using clock_t to store time
clock_t start, end;
// Quick sort
start = clock();
quickSort(a, 0, n - 1);
end = clock();
// Calculate the time taken for sorting
time[it] = ((double)(end - start)) / CLOCKS_PER_SEC;
// Print the size of the array and the time taken for sorting
printf("%li, %f\n", n, time[it]);
// Increase the size of array by 10000
n += 10000;
}
return 0;
}