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 turn: 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).

Previous: Merge sort Next: Counting sort