Quicksort

Why it exists

Quicksort is the sorting method used most in practice: it sorts in place, needs only a small stack, and its inner loop is very short, so on average it beats merge sort and heap sort by a constant factor. Its weakness is a worst case of $\Theta(n^2)$ on unlucky inputs, and GATE tests exactly this contrast: which inputs are bad, what the recurrence is, and why the average case is still $n \log n$.

Prerequisites

You need divide and conquer and the recurrence $T(n) = T(k) + T(n - k - 1) + \Theta(n)$ (divide and conquer).

Precise definitions

Partition. Choose one key, the pivot, and rearrange a range so that every key to the left of the pivot's final position is $\le$ the pivot and every key to the right is $>$ it (Lomuto) or $\ge$ it (Hoare). After a Lomuto partition (below) the pivot is in its final sorted position; Hoare's original partition instead returns a split point, with every key on the left $\le$ every key on the right.

Quicksort. Partition the range, then sort the part left of the pivot and the part right of the pivot recursively. There is no merge step: when both recursive calls return the range is sorted.

Lomuto partition (used on this page). The pivot is the last key $a_{hi}$. A boundary $i$ keeps the invariant: positions $lo..i$ hold keys $\le$ pivot, positions $i + 1..j - 1$ hold keys $>$ pivot, positions $j..hi - 1$ are unexamined. Scan $j$ from $lo$ to $hi - 1$; if $a_j \le$ pivot, increase $i$ and swap $a_i$ with $a_j$. At the end swap the pivot into position $i + 1$. It makes exactly $hi - lo$ comparisons.

Hoare partition (the original). Two indices start at the two ends and move towards each other; the left one stops at a key $\ge$ pivot, the right one at a key $\le$ pivot, the two keys are swapped, and so on until the indices cross. It splits evenly when many keys are equal, because both indices stop on keys equal to the pivot.

Randomised quicksort. Choose the pivot uniformly at random among the keys of the range (for example swap a random key to the end first). The running time then depends on the random choices, not on the input order.

How it works

A real run. The animation sorts $6, 3, 8, 1, 7, 2, 5, 4$ with exactly the code shown. In each partition the pivot is the last key; the key under comparison is marked; whenever a key is not larger than the pivot it is swapped to the growing left part; at the end the pivot is swapped into its final place (green).

Where the cost is. One partition of $n$ keys makes $n - 1$ comparisons. If it splits the range into parts of sizes $k$ and $n - 1 - k$, then $T(n) = T(k) + T(n - 1 - k) + \Theta(n).$ Everything depends on the splits:

• Worst case: always $k = 0$ (the pivot is the smallest or the largest key): $T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)$, exactly $n(n-1)/2$ comparisons. For the last-element pivot this happens on sorted and on reverse sorted input, and with the Lomuto partition above (which sends keys equal to the pivot to the left) also when all keys are equal.
• Best case: always $k = \lfloor (n-1)/2 \rfloor$ (the pivot is the median): $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$.
• Any constant-fraction split: if every split is at most $9 : 1$, then $T(n) = T(n/10) + T(9n/10) + n$. The recursion tree has depth between $\log_{10} n$ and $\log_{10/9} n$ and every level costs at most $n$, so $T(n) = \Theta(n \log n)$. A split that is not perfect but is proportional is still fast.
• Average case: for a random order of distinct keys the expected number of comparisons is exactly $C(n) = 2(n + 1) H_n - 4n \approx 1.39\, n \log_2 n,\qquad H_n = 1 + \tfrac12 + \cdots + \tfrac1n,$ so $\Theta(n \log n)$, only about $39\%$ more comparisons than the best case.

Why the average is $2(n+1)H_n - 4n$. Call the keys $z_1 < z_2 < \cdots < z_n$ in sorted order. Two keys $z_i$ and $z_j$ are compared at most once, and they are compared exactly when one of them is the first pivot chosen among $z_i, z_{i+1}, \ldots, z_j$ (if a key strictly between them is chosen first, they are separated and never meet). For a random order each of these $j - i + 1$ keys is equally likely to be first, so the probability is $2/(j - i + 1)$. Summing over all pairs with $d = j - i + 1$ from $2$ to $n$ (there are $n + 1 - d$ pairs with this $d$): $C(n) = \sum_{d=2}^{n} (n + 1 - d) \frac{2}{d} = 2(n + 1)(H_n - 1) - 2(n - 1) = 2(n + 1)H_n - 4n .$ The same value solves the recurrence $C(n) = n - 1 + \frac{2}{n} \sum_{k=0}^{n-1} C(k)$.

Measured. The program below counts the comparisons of this very code on sorted, reversed, all-equal and random inputs. The random column is the average of $400$ random orders and is close to the exact expectation.

#include <stdio.h>
 
static long cmps;
 
static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
 
static int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++) {
        cmps++;
        if (a[j] <= pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[hi]);
    return i + 1;
}
 
static void quicksort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}
 
static long run(int a[], int n) {
    cmps = 0;
    quicksort(a, 0, n - 1);
    for (int i = 1; i < n; i++) if (a[i - 1] > a[i]) return -1;
    return cmps;
}
 
int main(void) {
    static int a[1024];
    int ns[] = {16, 64, 256, 1024};
    unsigned s = 99;
    printf("%5s %9s %9s %9s %12s\n", "n", "sorted", "reversed", "all-equal", "random-total");
    for (int q = 0; q < 4; q++) {
        int n = ns[q];
        for (int i = 0; i < n; i++) a[i] = i;
        long c1 = run(a, n);
        for (int i = 0; i < n; i++) a[i] = n - i;
        long c2 = run(a, n);
        for (int i = 0; i < n; i++) a[i] = 7;
        long c3 = run(a, n);
        long total = 0;                                   /* 400 random permutations: Fisher-Yates with a simple generator */
        for (int trial = 0; trial < 400; trial++) {
            for (int i = 0; i < n; i++) a[i] = i;
            for (int i = n - 1; i > 0; i--) { s = s * 1103515245u + 12345u; int j = (int)((s >> 8) % (unsigned)(i + 1)); swap(&a[i], &a[j]); }
            total += run(a, n);
        }
        printf("%5d %9ld %9ld %9ld %12ld\n", n, c1, c2, c3, total);
    }
    return 0;
}

    n    sorted  reversed all-equal random-total
   16       120       120       120        20509
   64      2016      2016      2016       144000
  256     32640     32640     32640       850120
 1024    523776    523776    523776      4521100

Choosing the pivot. A fixed rule (first, last) is defeated by sorted input, which is common in practice. Remedies: choose a random key (expected $2(n+1)H_n - 4n$ comparisons for every input, because the randomness is in the algorithm), or the median of three (first, middle, last keys), or the true median found in linear time by the median-of-medians method (divide and conquer applications), which makes the worst case $\Theta(n \log n)$ at the price of a large constant.

Stack space. The recursion depth is the height of the recursion tree: $\Theta(\log n)$ for balanced splits and $n - 1$ for the worst case. The space of quicksort is therefore $O(\log n)$ on average but $O(n)$ in the worst case, unless the algorithm recurses on the smaller part and handles the larger part in a loop (tail-call elimination): each recursive call then handles at most half of the keys, so the depth is at most $\lfloor \log_2 n \rfloor + 1$, whatever the input.

Equal keys. The Lomuto partition above sends equal keys to the left, so a range of equal keys splits $0 : (n - 1)$ every time and costs $\Theta(n^2)$ (the table shows $n(n-1)/2$ for all-equal input). Hoare's partition stops on equal keys and splits such a range in the middle. The three-way partition (keys $<$, $=$, $>$ the pivot) puts all keys equal to the pivot in place at once, which makes all-equal input take $\Theta(n)$.

Properties. In place (apart from the stack); not stable (the partition swaps keys across the pivot, over equal keys); not adaptive in the sense of insertion sort (sorted input is the worst case for the simple pivot rules); average $\Theta(n \log n)$, worst case $\Theta(n^2)$. Practical versions switch to insertion sort for ranges below about ten keys.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Quicksort is an instance of divide and conquer with all the work in the divide step; its recurrence is solved with the methods of solving recurrences. Compare it with merge sort and heap sort in stability and comparison of sorts. Its partition also finds the $k$-th smallest key in expected linear time (quickselect, divide and conquer applications).

PYQs

An array of 25 distinct elements is to be sorted
using quicksort. Assume that the pivot element is
chosen uniformly at random. The probability that
the pivot element gets placed in the worst possible
location in the first round of partitioning (rounded
off to 2 decimal places) is

The worst-case running time of Insertion sort,
Merge sort and Quick sort, respectively, are:

Suppose you are provided with the following
function declaration in the C programming
language.
int partition(int a[ ], int n);
The function treats the first element of a[] as a
pivot, and rearranges the array so that all elements
less than or equal to the pivot is in the left part of
the array, and all elements greater than the pivot
is in the right part. In addition, it moves the pivot
so that the pivot is the last element of the left part.
The return value is the number of elements in the
left part. The following partially given function in
the C programming language is used to find the
k-th smallest element in an array a[ ] of size n
using the partition function. We assume k <= n
C
int kth_smallest(int a[], int n, int k)
{
int left_end = partition(a, n);
if ( left_end+1 == k ){
return a[left_end];
}
if ( left_end+1 > k ){
return kth_smallest(
);
} else {
return kth_smallest(
);
}
}
The missing arguments lists are respectively

Which one of the following is the recurrence
equation for the worst case time complexity of the
Quicksort algorithm for sorting n ( >=2) numbers?
In the recurrence equations given in the options
below, c is a constant.

You have an array of n elements. Suppose you
implement quick sort by always choosing the
central element of the array as the pivot. Then the
tightest upper bound for the worst case
performance is

Let P is a quick sort program to sort numbers in
ascending order using the first element as the pivot.
Let t1 and t2 be the number of comparisons made by
P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively.
Which one of the following holds?

In quick sort, for sorting n elements, the (n/4)th
smallest element is selected as pivot using an
O(n) time algorithm. What is the worst case time
complexity of the quick sort?

Self-check

Revision card

References