2.
Write C/C++ programs 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 non graph sheet. The
elements can be read from a file or can be generated using the random number generator.
Demonstrate using C/C++ how the divide-and-conquer method works along with its time
complexity analysis: worst case, average case and best case.
// C program to implement Quick Sort Algorithm
#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
int partition(int arr[], int low, int high)
{
// initialize pivot to be the first element
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
// condition 1: find the first element greater than
// the pivot (from starting)
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
// condition 2: find the first element smaller than
// the pivot (from last)
while (arr[j] > pivot && j >= low + 1) {
j--;
}
if (i < j) {
swap(&arr[i], &arr[j]);
}
}
swap(&arr[low], &arr[j]);
return j;
}
// QuickSort function
void quickSort(int arr[], int low, int high)
{
if (low < high) {
// call Partition function to find Partition Index
int partitionIndex = partition(arr, low, high);
// Recursively call quickSort() for left and right
// half based on partition Index
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
// driver code
int main()
{
int n, i;
clock_t start, end;
double time_taken;
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
int arr[n];
printf("Generating %d random elements...\n", n);
srand(time(NULL)); // Seed for random number generator
for(i = 0; i < n; i++)
{
arr[i] = rand() % 10000; // Generate random integers between 0 and 9999
}
printf("Sorting the array using Quick Sort...\n");
start = clock(); // Start timer
quickSort(arr, 0, n - 1);
end = clock(); // Stop timer
// printing the sorted array
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void quick_sort(int[], int, int);
int partition(int[], int, int);
int main()
{
int n, i;
clock_t start, end;
double time_taken;
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
int arr[n];
printf("Generating %d random elements...\n", n);
srand(time(NULL)); // Seed for random number generator
for(i = 0; i < n; i++)
{
arr[i] = rand() % 10000; // Generate random integers between 0 and 9999
}
printf("Sorting the array using Quick Sort...\n");
start = clock(); // Start timer
quick_sort(arr, 0, n - 1);
end = clock(); // Stop timer
printf("Sorted array: \n");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
time_taken = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort %d elements: %lf seconds", n, time_taken);
return 0;
}
void quick_sort(int arr[], int low, int high)
{
int pivot_index;
if(low < high)
{
pivot_index = partition(arr, low, high);
quick_sort(arr, low, pivot_index - 1);
quick_sort(arr, pivot_index + 1, high);
}
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = low - 1, j, temp;
for(j = low; j < high; j++)
{
if(arr[j] <= pivot)
{
i++;
// Swap arr[i] and arr[j]
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i + 1] and arr[high]
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
The above program generates an array of n random integers between 0 and 9999
using the rand() function from the stdlib.h library. It then sorts the array using the
quick_sort() function and records the time taken using the clock() function from
the time.h library.
The quick_sort() function implements the Quick Sort algorithm using the
partition() function to determine the pivot index. The function recursively sorts the
two partitions of the array on either side of the pivot index.
The time complexity of Quick Sort algorithm can be analyzed using three cases:
worst case, average case, and best case.
Worst Case: The worst case occurs when the partitioning process always picks the
greatest or smallest element as the pivot. In this case, the algorithm makes n - 1
comparisons at each level of recursion, resulting in a time complexity of O(n^2).
Average Case: The average case occurs when the pivot is chosen randomly and the
partition divides the array roughly into two equal parts. In this case, the time
complexity is O(n log n).
Best Case: The best case occurs when the partitioning process always picks the
median element as the pivot. In this case, the algorithm makes log n comparisons
at each level of recursion, resulting in a time complexity of
