Lesson 14.3 · Sorting and Divide & Conquer
Quick Sort and Quickselect
Partition around a pivot so smaller values go left and larger go right, then recurse on both sides (sort) or only one side (select the kth).
16 min
Think of it like this
Sorting a class by height: pick one student as the pivot, send shorter students to their left and taller ones to their right. The pivot is now exactly where they belong. Repeat in each group.
1.Partitioning
Lomuto partition: choose a pivot (put it at the end), keep a boundary store; scan i over the range, and whenever a[i] < pivot, swap it to store and advance. Finally swap the pivot to store. Everything left of it is smaller, everything right is at least as big.
Average O(n log n); worst case O(n²) when pivots are always the smallest or largest (for example a sorted array with the last element as pivot). Choosing a random pivot makes the worst case extremely unlikely.
a = [7, 2, 1, 6, 4] (pivot = last = 4)Step 1/4Pivot 4. 7 isn't smaller: move on.
2.Quickselect: the kth element in O(n) average
After one partition, the pivot's final index p is known. If p is the index you want, you're done; otherwise recurse only into the side that contains it. Average work n + n/2 + n/4 + ... = O(n).
Remember
- Partition places the pivot at its final position.
- Random pivots avoid the O(n²) worst case.
- Quickselect recurses into one side: O(n) average.
Common mistakes
- Always choosing the first or last element as pivot on sorted input.
- Not handling many equal elements (three-way partitioning helps).