Quick sort

Introduction

Quick sort is divide and conquer the other way round from merge sort: the hard work happens before the recursive calls, and combining needs nothing at all. It is usually the fastest sort in practice, and C's qsort is named after it.

Merge sort does its real work after the recursive calls. Quick sort does it before them, so once both sides are sorted there is nothing left to do. It is also a good example of an algorithm whose average case is much better than its worst case.

How it works

Partition

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int a[], int lo, int hi) {
    int pivot = a[hi];
    int i = lo;                    // a[lo .. i-1] are smaller than the pivot
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            swap(&a[i], &a[j]);
            i++;
        }
    }
    swap(&a[i], &a[hi]);           // the pivot goes between the two parts
    return i;
}

int main(void) {
    int a[] = {7, 2, 9, 4, 3, 8, 5};
    int p = partition(a, 0, 6);
    for (int k = 0; k < 7; k++) printf("%d ", a[k]);
    printf("\npivot 5 is now at index %d\n", p);
    return 0;
}

Partitioning picks a pivot (here the last item, the Lomuto scheme) and rearranges the array so that smaller items come first, then the pivot, then the rest. The pivot is then in its final sorted place.

i marks the end of the "smaller than the pivot" part. j scans every other item; each item smaller than the pivot is swapped into the small part, which grows by one. Finally the pivot is swapped to position i. Watch the two parts grow.

Good and bad pivots

If each pivot splits the range roughly in half, there are about log₂ n levels of O(n) partitioning: O(n log n). But with the last item as pivot, an array that is already sorted splits into n - 1 items and 0 items every time: n levels, O(n²). Real implementations avoid that by choosing a random pivot, or the median of the first, middle and last items.

Syntax

int p = partition(a, lo, hi);   // the pivot lands at index p
quick_sort(a, lo, p - 1);       // everything smaller
quick_sort(a, p + 1, hi);       // everything else

Example

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int a[], int lo, int hi) {
    int pivot = a[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            swap(&a[i], &a[j]);
            i++;
        }
    }
    swap(&a[i], &a[hi]);
    return i;
}

void quick_sort(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quick_sort(a, lo, p - 1);
    quick_sort(a, p + 1, hi);
}

int main(void) {
    int a[] = {10, 7, 8, 9, 1, 5};
    quick_sort(a, 0, 5);
    for (int k = 0; k < 6; k++) printf("%d ", a[k]);
    printf("\n");
    return 0;
}

After partitioning, sort the part left of the pivot and the part right of it, recursively. They never need merging: everything left is already smaller than everything right.

Line by line

1. swap exchanges two integers through their addresses.
2. partition takes the last item as the pivot, and i marks where the next smaller item should go.
3. The for loop scans each other item, and each one smaller than the pivot is swapped into the small part.
4. The final swap puts the pivot between the two parts, and its index is returned.
5. quick_sort stops on a range of 0 or 1 items. Otherwise it partitions, then sorts both sides, leaving out index p.
6. main sorts six numbers in place and prints them.

Expected result

1 5 7 8 9 10 

In the real world

C's qsort is named after this algorithm, though the C standard does not say which method a library must use. Many standard libraries use introsort, which starts as quick sort and switches to heap sort if the recursion gets too deep, so that the O(n²) case cannot happen.

Common mistakes

• Recursing on lo .. p instead of lo .. p - 1: the pivot is included again and the recursion may never shrink.
• Forgetting the final swap that puts the pivot in place.
• Always taking the first or last item as the pivot on data that may already be sorted, which gives the O(n²) case.

Best practices

• Choose a random pivot, or the median of three items, on real data.
• Test with sorted input, reversed input and many equal values.
• Recurse into the smaller side first if deep recursion is a risk.

Summary

Quick sort partitions a range around a pivot and sorts the two sides, with nothing to combine afterwards. It averages O(n log n), and good pivot choices keep it away from its O(n²) worst case.

Mark lesson complete