Quick Sort is a highly efficient, comparison-based, divide-and-conquer sorting algorithm. It works by selecting a pivot element, partitioning the array around the pivot so that smaller elements go to the left and larger elements go to the right, and then recursively sorting the sub-arrays. Quick Sort has an average time complexity of O(n log n) and is often faster than Merge Sort for arrays stored in memory.
Understanding the Problem
The main challenge in Quick Sort is choosing the pivot and partitioning the array correctly. A good pivot ensures balanced partitions, while a poor choice can degrade performance to O(n²). Proper handling of recursion and array boundaries is essential to avoid infinite loops or incorrect sorting.
Program 1: Recursive Quick Sort
This program demonstrates Quick Sort with recursion and Lomuto partitioning scheme.
#include <stdio.h>
// Function to swap two integers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function (Lomuto scheme)
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose last element as pivot
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Recursive Quick Sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partition index
quickSort(arr, low, pi - 1); // Sort left sub-array
quickSort(arr, pi + 1, high); // Sort right sub-array
}
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
quickSort(arr, 0, size - 1);
printf("Sorted array: ");
display(arr, size);
return 0;
}This program selects the last element as the pivot and partitions the array around it. Recursive calls sort the left and right sub-arrays, gradually producing a fully sorted array.
Program 2: Quick Sort with Hoare Partitioning
This variation uses Hoare’s partition scheme, which can reduce swaps and often performs slightly faster than Lomuto partitioning.
#include <stdio.h>
// Function to swap two integers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function (Hoare scheme)
int partitionHoare(int arr[], int low, int high) {
int pivot = arr[low]; // Choose first element as pivot
int i = low - 1;
int j = high + 1;
while (1) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
swap(&arr[i], &arr[j]);
}
}
// Recursive Quick Sort function using Hoare partition
void quickSortHoare(int arr[], int low, int high) {
if (low < high) {
int pi = partitionHoare(arr, low, high);
quickSortHoare(arr, low, pi);
quickSortHoare(arr, pi + 1, high);
}
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
quickSortHoare(arr, 0, size - 1);
printf("Sorted array: ");
display(arr, size);
return 0;
}Hoare’s partitioning reduces swaps and often results in slightly faster sorting, especially on large arrays. It demonstrates an alternative approach to pivot-based partitioning in Quick Sort.
FAQs
Q1: What is the time complexity of Quick Sort?
Average and best case: O(n log n), worst case: O(n²) (unbalanced partitions).
Q2: Is Quick Sort stable?
No, Quick Sort is generally not stable.
Q3: How to avoid worst-case performance?
Randomly selecting the pivot or using the median-of-three method reduces the chance of unbalanced partitions.
Q4: Does Quick Sort require extra memory?
It is an in-place sorting algorithm, so it requires O(log n) extra space for recursion.
Conclusion
Quick Sort is one of the fastest general-purpose sorting algorithms for arrays in memory. Its efficiency depends on balanced partitioning and proper recursion. Both Lomuto and Hoare partitioning schemes demonstrate how different pivot strategies affect performance and the number of swaps.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A respected and traditional textbook covering essential C concepts and core data structures, including quick sort.
- Quick Sort – GeeksforGeeks – Clear explanation of the quick sort algorithm using the divide-and-conquer strategy, detailing pivot selection, partitioning, recursion, and base cases.
- Quick Sort – Programiz – Practical step-by-step guide featuring a working principle explanation, pseudocode, and various language examples (including C).
- Exploring the Time and Space Complexities of Quick Sort – Programiz PRO – Thoughtful breakdown of quick sort’s time complexity (best: O(n log n); average: O(n log n); worst: O(n²)) and its space usage (average: O(log n), worst can reach O(n)).
