1. Introduction
Quick sort is a highly efficient, in-place, divide-and-conquer sorting algorithm widely used in practice (it underlies many standard library sort functions). Instead of merging sorted halves like merge sort, quick sort works by selecting a 'pivot' element and partitioning the array so that all elements smaller than the pivot come before it and all elements greater come after it. The pivot then sits in its final sorted position, and the same process is recursively applied to the sub-arrays on either side. On average, quick sort runs in O(n log n) time and requires only O(log n) extra space for recursion, making it faster in practice than merge sort despite sharing the same average-case complexity class.
Cricket analogy: Quick sort is like seeding an IPL knockout bracket around one benchmark team, the pivot, teams weaker go to one side, stronger to the other, and each side is then re-seeded the same way until the whole bracket is sorted.
2. Syntax
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
/* Parameters:
arr - array of integers to sort in place
low - starting index of the current sub-array
high - ending index of the current sub-array
Initial call: quickSort(arr, 0, n - 1); */3. Explanation
This implementation uses the Lomuto partition scheme with the last element as the pivot. partition() picks arr[high] as the pivot, then uses an index i to track the boundary of elements known to be smaller than the pivot. It scans j from low to high - 1; whenever arr[j] < pivot, it increments i and swaps arr[i] with arr[j], growing the 'smaller than pivot' region. After the scan, it swaps arr[i + 1] with arr[high], placing the pivot right after the smaller elements and before the larger ones, and returns i + 1 as the pivot's final sorted index. quickSort() then recursively sorts the sub-array to the left of the pivot (low to pivotIndex - 1) and to the right (pivotIndex + 1 to high).
Cricket analogy: The Lomuto partition is like a selector using the last player trialed as the benchmark (pivot), keeping an index of confirmed squad members (i) while scanning remaining trialists (j), swapping in anyone better than the benchmark, then slotting the benchmark player right after the confirmed group.
Worked trace on [10, 7, 8, 9, 1, 5] with pivot = arr[high] = 5: i starts at -1. j=0: arr[0]=10, not < 5, skip. j=1: arr[1]=7, not < 5, skip. j=2: arr[2]=8, not < 5, skip. j=3: arr[3]=9, not < 5, skip. j=4: arr[4]=1, 1 < 5, so i becomes 0, swap arr[0] and arr[4] -> [1,7,8,9,10,5]. Loop ends; swap arr[i+1]=arr[1] with arr[high]=arr[5] -> [1,5,8,9,10,7]. Pivot 5 is now at index 1, its correct sorted position, with quickSort then recursing on [1] (left, already sorted) and [8,9,10,7] (right, indices 2-5).
Cricket analogy: Tracing quick sort on scores [10,7,8,9,1,5] with pivot 5 is like a selector scanning five trialists' fitness scores against a benchmark of 5, finding only the score of 1 beats it, swapping it forward, then placing the benchmark 5 right after it, leaving [1,5,8,9,10,7] with 5 correctly seated at index 1.
4. Example
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
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;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main(void) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printArray(arr, n);
return 0;
}5. Output
1 5 7 8 9 106. Key Takeaways
- Average-case time complexity is O(n log n), which is what makes quick sort practical for general-purpose use.
- Worst-case time complexity is O(n^2), which occurs when the pivot is repeatedly the smallest or largest element (e.g., an already-sorted array with last-element pivoting).
- Quick sort is an in-place algorithm requiring only O(log n) extra space for the recursion stack (average case).
- It is not a stable sort by default, since the partition step can reorder equal elements.
- Randomized or median-of-three pivot selection helps avoid the O(n^2) worst case on already-sorted input.
Practice what you learned
1. What is the average-case time complexity of quick sort?
2. When does quick sort's worst-case O(n^2) behavior typically occur?
3. In the Lomuto partition scheme shown, what does the returned index represent?
4. What is the space complexity of quick sort's recursion in the average case?
5. Is the quick sort implementation shown in the example a stable sort?
Was this page helpful?
You May Also Like
Merge Sort in C
Understand merge sort in C: divide-and-conquer recursion, syntax, a worked merge-step trace, full code, output, and O(n log n) complexity.
Bubble Sort in C
Master bubble sort in C: syntax, algorithm explanation, optimized code with early-exit flag, sample output, and O(n^2) complexity.
Binary Search in C
Learn binary search in C with syntax, a step-by-step explanation, working code, output, and O(log n) complexity analysis.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics