Quicksort in C++

This is the first of the **Runnable Notes** - short algorithm write-ups where every snippet actually runs in your browser. No copy-paste into an IDE: **run the snippet below**, change a number, run it again.

The same runner lives at `/playground`. The site itself is a [forkable template](https://github.com/crazycloudcc/ccblog/generate).

**Quicksort** sorts in-place by picking a pivot, partitioning the array into values smaller and larger, then recursing on each side. Average `O(n log n)`, worst case `O(n^2)`.

The partition step

Everything interesting happens in `partition` - pick a pivot, sweep the range, and end with the pivot in its final sorted position:

1int partition(std::vector<int>& a, int lo, int hi) {
2    int pivot = a[hi];
3    int i = lo - 1;
4    for (int j = lo; j < hi; j++) {
5        if (a[j] <= pivot) {
6            i++;
7            std::swap(a[i], a[j]);
8        }
9    }
10    std::swap(a[i + 1], a[hi]);
11    return i + 1;
12}

After `partition` returns `p`, everything at indices `<= p` is `<= pivot` and the pivot itself is fixed. Recurse on `[lo, p-1]` and `[p+1, hi]` until the range is empty.

Pivot choice matters

The pivot decides how balanced the recursion is. Picking the last element (above) is simple and correct, but the classic trap is picking the first element on already-sorted input - one side is empty every time, and you recurse `n` deep:

int pivot = a[hi];   // last element: balanced on random input

For random data the choice barely matters. For hostile or nearly-sorted data, randomize the pivot or use median-of-three.

Run it

The full program reads `n`, then `n` integers, and prints them sorted. It runs right here - edit the code, change the stdin, hit run:

A run looks like this - the four compile phases, then the sorted output on stdout:

stdout
1 1 3 4 5

Try it

Paste into the stdin box and run:

| stdin | expected stdout | |-------|-----------------| | `5` then `3 1 4 1 5` | `1 1 3 4 5` | | `6` then `6 5 4 3 2 1` | `1 2 3 4 5 6` | | `4` then `2 2 2 2` | `2 2 2 2` |

The first run is slower - that is the one-time WASM toolchain fetch. After that, runs drop to tens of milliseconds.

Next in the series: **Binary Search** - the divide-and-conquer counterpart, where the pivot choice is fixed and the trap is off-by-one.

中文导览（同一套 runner）：[在浏览器里编译运行 C++](/blog/liulanqi-bianyi-cpp)。