Step 3 of 6

Quicksort and partitioning

Quicksort also divides and conquers, but does the hard work before recursing instead of after:

1. Pick a pivot element.
2. Partition: rearrange so everything smaller than the pivot comes before it and everything else after. The pivot is now in its final position.
3. Recursively sort the part before the pivot and the part after it. No merge step is needed.

The Lomuto partition, using the last element as the pivot:

pivot = v[hi]; i = lo
for j in lo..hi-1:
    if v[j] < pivot: swap(v[i], v[j]); i++
swap(v[i], v[hi])     // pivot lands at its final position i
return i

Here's one partition step, printed, on letters:

#include <iostream>
#include <string>
#include <utility>

int partition(std::string& s, int lo, int hi) {
    char pivot = s[hi];
    int i = lo;                              // s[lo..i) holds letters < pivot
    for (int j = lo; j < hi; j++) {
        if (s[j] < pivot) {
            std::swap(s[i], s[j]);
            i++;
        }
    }
    std::swap(s[i], s[hi]);
    return i;
}

int main() {
    std::string s = "qjxbmae";
    std::cout << s << "  pivot " << s.back() << "\n";
    int p = partition(s, 0, (int)s.size() - 1);
    std::cout << s << "  pivot now at " << p << "\n";
}

qjxbmae  pivot e
baeqmjx  pivot now at 2

Reading the result

After partitioning, e sits at index 2, with the smaller letters b a before it and the larger q m j x after it. Neither side is sorted yet, but e is exactly where it belongs in the final order. Quicksort now recurses on [0, 1] and [3, 6].

The invariant that makes Lomuto work: everything in s[lo..i) is smaller than the pivot. Each time a smaller element is found, it's swapped to position i and the boundary moves right.

Properties

• O(n log n) on average, in place, and very fast in practice thanks to good cache behavior.
• O(n²) worst case with bad pivots, for example always taking the last element of already-sorted data: every partition then splits off just one element. That's why real implementations pick pivots carefully, and std::sort falls back to heapsort when recursion gets too deep ("introsort").
• Not stable.

Your task

partition is the loop above on a std::vector<int>. quick_sort(v, lo, hi) returns when lo >= hi (zero or one element); otherwise it partitions, getting p, and recurses on lo..p-1 and p+1..hi. Note that the pivot itself is excluded from both recursive calls, which guarantees progress.

Your task

Write int partition(std::vector<int>& v, int lo, int hi) (inclusive range) and void quick_sort(std::vector<int>& v, int lo, int hi).

Challenge 2

Write void sort_colors(std::vector<int>& v) for values that are only 0, 1 or 2, in one pass with three pointers (the Dutch national flag): everything before lo is 0, everything after hi is 2, and mid scans the unknown part in between.

Challenge 3

Plain two-way partitioning is O(n²) when almost every value is the same. Write void quick_sort3(std::vector<int>& v, int lo, int hi) (inclusive range) with three-way partitioning: take the middle element as the pivot and split the range into less than, equal to and greater than it, then recurse only on the outer two parts. The test sorts 200,000 values that are all 0, 1 or 2.

Previous: Merge sort Next: Counting sort