Pick one value, the pivot. Put everything smaller on its left and everything larger on its right, and the pivot is where it belongs. Watch each side repeat.
Splitting around a pivot
Ten numbers partitioned round the last value, then each side again
static void swap(int *a, int *b){ int t = *a; *a = *b; *b = t;} static int partition(int *a, int lo, int hi){ int pivot = a[hi]; int i = lo; for (int j = lo; j < hi; j++) { comparisons++; if (a[j] < pivot) { swap(&a[i], &a[j]); i++; } } swap(&a[i], &a[hi]); return i;} static void quicksort(int *a, int lo, int hi){ if (lo >= hi) return; int p = partition(a, lo, hi); quicksort(a, lo, p - 1); quicksort(a, p + 1, hi);}main has started: a has room for ten ints.
- calls
- 0
- comparisons
- 0
- depth
- 0
Output
Describe this picture
Two pictures stacked, with the code beside them, the line about to run marked. At the top, a tree of calls to quicksort, one circle per call, labelled with its range: 0–9 at the root, one number for a single cell, an empty circle for an empty range. Below it, the ten cells of int a[10] as bars: 6 2 9 1 5 10 3 8 4 7. The clip takes about 35 seconds. While a call partitions its range, the cells outside the range grey, and the last bar, the pivot, is toned: 7 first. The marker j under the bars moves right one cell per comparison, its bar tinted. The marker i over the bars marks where the next smaller value goes: when the bar at j is smaller than the pivot, it swaps to i (a cell swapped with itself does not move) and i moves on. The bars left of i, all smaller than the pivot, are tinted. When j reaches the pivot, the pivot swaps into cell i and greys there for good: 7 lands in cell 6, with 6 2 1 5 3 4 on its left and 8 10 9 on its right. Then the left side repeats with pivot 4, and so on down, and then the right side with pivot 9; 13 calls in all, five deep at most. Under the picture are one sentence on the current step and the readouts “calls”, “comparisons” and “depth”; comparisons end at 20. After the clip, the control “Starting order” picks Random (the house array) or Already sorted, and a press replays on that order. With sorted input every pivot is the largest value of its range and nothing moves: partitions of 9, 8, …, 1 comparisons, a staircase of ten calls down the left of the tree, depth 10, 45 comparisons. The transport plays and pauses, steps one beat back or forward, and scrubs; the order and a paused step are kept in the page address as quicksort.order and quicksort.step.
The pivot’s place
Choose a value from the range, the pivot; here it is always the last one. Partitioning rearranges the range so that every value smaller than the pivot comes before it and every other value after it. The pivot then sits in the cell it will hold in the sorted array: exactly the smaller values are before it. Neither side is sorted yet, but no value will ever cross the pivot again, so each side can be sorted on its own, by the same method.
All the work is in the partitions, on the way down; there is nothing to combine afterwards. That is the mirror image of Merge sort, which splits without looking and does its work in the merges.
The code and its cost
static int partition(int *a, int lo, int hi)
{
int pivot = a[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
comparisons++;
if (a[j] < pivot) {
swap(&a[i], &a[j]);
i++;
}
}
swap(&a[i], &a[hi]);
return i;
}
static void quicksort(int *a, int lo, int hi)
{
if (lo >= hi)
return;
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}This is Lomuto’s partition. It keeps one fact true as j sweeps: every value in a[lo] to a[i − 1] is smaller than the pivot, and every value in a[i] to a[j − 1] is not. A smaller a[j] is swapped to a[i], and i moves on. When j reaches hi, a[i] is the first value that is not smaller, so swapping the pivot there puts it in its place, and partition returns that place. A partition of m values makes m − 1 comparisons.
The house array
| Range | Pivot | After the partition | Comparisons |
|---|---|---|---|
| 0–9 | 7 | 6 2 1 5 3 4 · 7 · 8 10 9 | 9 |
| 0–5 | 4 | 2 1 3 · 4 · 6 5 | 5 |
| 0–2 | 3 | 2 1 · 3 | 2 |
| 0–1 | 1 | 1 · 2 | 1 |
| 4–5 | 5 | 5 · 6 | 1 |
| 7–9 | 9 | 8 · 9 · 10 | 2 |
quick.c prints 20 comparisons.
Average and worst
Each partition costs about the length of its range. If the pivot splits its range in half each time, there are about log₂ n levels, each costing about n, as in merge sort. For random input the average is exactly 2(n + 1)H_n − 4n comparisons, where H_n = 1 + 1/2 + … + 1/n. That grows like 1.39 n log₂ n. For n = 10 it is about 24.4, so the house array’s 20 is a lucky draw.
The worst case is when every pivot is the smallest or largest value of its range. Then one side is empty and the other has m − 1 values, and the partitions cost (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. With the last value as pivot, sorted input does exactly that: quick.c with -DORDER=1 makes 45 comparisons, with calls ten deep. Quicksort is not always n log n.
Random pivots
Sorted input is common, so a fixed pivot rule is a risk. random-pivot.c first swaps a randomly chosen value of the range into a[hi], then partitions as before. It draws with its own generator from a fixed seed, so every run gives the same counts: 20 comparisons on the house array, and 25 on sorted input instead of 45.
With a random pivot no input is bad in advance. For every input the expected number of comparisons, averaged over the program’s own random choices, is the same 2(n + 1)H_n − 4n (Expected value). A slow run is still possible, but only by bad luck, not because of the data. That holds for distinct keys. If every key is equal, this partition puts them all on one side whatever the pivot, and quicksort makes about n²/2 comparisons even with random pivots.
The stack and Hoare’s scheme
The calls nest as deep as the chain of unbalanced splits: ten on sorted input, n in general, and each call takes a stack frame. The fix is to recurse into the smaller side and handle the larger side with a loop. The smaller side has at most half the values, so the depth stays at most about log₂ n.
Hoare’s partition, the original one, moves two indices inwards from both ends and swaps a pair when both have stopped on a value on the wrong side. It swaps fewer times than Lomuto’s. In return its code is more delicate, and the pivot does not necessarily end in its final place.
Quicksort is in place, apart from the stack. It is not stable: a swap can carry a value past an equal one.
qsort
The C library sorts any array with qsort(base, n, size, compare). It knows nothing about the items: it gets their address, their number and their size, and a function that compares two of them through const void * pointers. That function returns a negative number, zero or a positive number. From people.c:
struct person {
const char *name;
int age;
};
static int by_age(const void *x, const void *y)
{
const struct person *a = x;
const struct person *b = y;
return (a->age > b->age) - (a->age < b->age);
}qsort(people, 4, sizeof people[0], by_age) sorts Ada 36, Lin 29, Sam 41 and Kai 23 into Kai 23, Lin 29, Ada 36, Sam 41. The ages are all different because qsort is not required to be stable. The C standard does not say which algorithm qsort uses, only what it must do.
Worked example
Why not return a->age - b->age? For ages it would work. In general it does not. Take −2,000,000,000 and 2,000,000,000: the true difference, −4,000,000,000, does not fit in an int. Signed overflow is undefined behaviour in C. On this machine the subtraction commonly wraps to 294,967,296, a positive number, which claims the first value is the larger. subtract-compare.c does the subtraction with wrapping on purpose and prints wrapped to int: 294967296, while the comparison form prints -1.
A thousand values. On random input the average is 2 × 1,001 × H_1000 − 4,000 ≈ 2 × 1,001 × 7.4855 − 4,000 ≈ 10,986 comparisons, with H_1000 ≈ 7.4855. The worst case is 1,000 × 999 / 2 = 499,500.
Two checks. How many comparisons does one Lomuto partition of n values make? (n − 1.) Is quicksort stable? (No.)
Where it’s used
The C library’s qsort, which many implementations build on quicksort.
Introsort, the sort in other standard libraries: quicksort that switches to Heapsort when the calls get too deep, so the worst case stays O(n log n).
Finding the k-th smallest value. Quickselect partitions once and recurses into the one side that holds position k: linear time on average.
Reference card
| Code or idea | Meaning |
|---|---|
partition(a, lo, hi) | Lomuto: pivot a[hi]; smaller values to the left of i; pivot into a[i]; return i |
| after a partition | the pivot is in its final place |
| one partition of m values | m − 1 comparisons |
| average, random input | 2(n + 1)H_n − 4n, about 1.39 n log₂ n |
| worst case | n(n − 1)/2, every pivot an extreme (sorted input, last-value pivot) |
| random pivot | the average expected for every input |
| smaller side first | stack depth at most about log₂ n |
qsort(base, n, size, compare) | the C library’s sort; compare returns < 0, 0 or > 0 |
| in place, stable | yes (apart from the stack), no |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.