Unit 2.2 · about 5 h
97 / 324Partitioning, quicksort, quickselect and top-k
Partitioning is the one primitive behind quicksort, quickselect and three-way color sorts. Its invariant decides whether equal keys cost linear or quadratic time.
- derive
- implement
You can now
- State the Lomuto partition invariant and maintain it while coding, including the duplicate-key behavior.
- Implement randomized quicksort and iterative quickselect with differential tests, and show they degenerate without a random pivot or three-way partition on adversarial input.
- Pick between a heap, quickselect and full sort for a top-k task from streaming, sorted-output and mutation constraints.
Covers
- Partition invariants, quicksort and adversarial pivots
- Selection, quickselect and top-k trade-offs
Study, in this order
5 steps
- Comparison sorts II: quicksort, partition, and the production hybridsDSA Handbook - search, trees and heaps
Algorithm A: quicksort with median-of-three Lomuto partition; Why the obvious version explodes on sorted input; The teaching reference; Worked example: median-of-three Lomuto on
[5,2,4,7,1,3,2,6]; Cost; Pitfalls - Erickson Chapter 1: QuicksortAlgorithms
Section 1.5 Quicksort (pp. 29 to 31), including the Lomuto Partition pseudocode and the pivot-rank recurrence
- Quickselect: linear-time selectionDSA Handbook - search, trees and heaps
The primitive: partition; The trick: recurse on one side; Random pivot is non-negotiable; Worked example: LC 215 on
[3,2,1,5,6,4],k=2; Quickselect or heap?; PitfallsDepth · Read Why expected linear works for the recurrence shape only; its expectation proof belongs to algorithms/decomposition-greedy-randomness/randomized-algorithms. Skim Why nobody ships median-of-medians for the verdict; the deterministic proof belongs to algorithms/decomposition-greedy-randomness/divide-conquer-recurrences.
- Erickson Chapter 1: Quickselect and good pivotsAlgorithms
Section 1.8 Linear-Time Selection (pp. 35 to 36), Quickselect and Good pivots
Depth · Stop before the Analysis on pp. 37 to 38; the median-of-medians proof belongs to algorithms/decomposition-greedy-randomness/divide-conquer-recurrences.
- Quickselect vs heap for top-KDSA Handbook Patterns - quickselect vs heap for top-K
The decision; Algorithms compared; Side-by-side; Common misconceptions
Focus on
- Lomuto invariant: at every scan step,
arr[lo..i]holds elements <= pivot,arr[i+1..j-1]holds elements > pivot, andarr[j..hi-1]is unexamined. The final swap puts the pivot at its final sorted index. Median-of-three places the pivot atarr[hi]; that placement is part of the contract. - With the handbook's
<=in the scan, keys equal to the pivot join the left band; Erickson's strict<sends them right. Either way all-equal input puts every key on one side, so Lomuto degenerates to \(\Theta(n^2)\) even with a random pivot. Three-way (Dutch flag) partition groups equal keys in one pass and recovers \(\Theta(n)\). - Random pivot is the correctness fix, not an optimization: a fixed last-element pivot is \(\Theta(n^2)\) on sorted input. Judges include large sorted and duplicate-heavy arrays, so test both yourself.
- Top-k routing: a stream or tiny \(k\) favors a size-k heap (\(O(n \log k)\) time, \(O(k)\) space, no mutation); a whole array in memory with unsorted output favors quickselect (expected \(O(n)\)); sorted output adds \(O(k \log k)\). In CPython,
heapq.nlargestruns in C: on a 12th Gen Intel Core i9-12900K with Python 3.13.14 it took about 1.3 ms against about 6 ms for an in-place pure-Python quickselect on 100,000 ints with \(k = 100\), so count comparisons and wall-clock time separately.
Reproduce closed-book
<= pivot, everything right of it > pivot). quickselect([3,2,1,5,6,4], 2) must return 5. Run a Hypothesis differential test against sorted on 300 lists up to length 40, including sorted and all-equal inputs, then add a three-way partition and time both on 10,000 equal keys.Traps
- Converting \(k\) wrong: kth largest wants target index \(n-k\), kth smallest wants \(k-1\). For \(n=6\), \(k=2\), the target index is 4.
- Quickselect mutates the caller's array. Copy at the boundary when the caller needs the input intact.
- Recursing into the wrong side after partition. The pivot sits at its final sorted position; only the side containing the target index is read again. The rest is partitioned, not sorted.
Practice
LeetCode 215: Kth Largest Element in an Array
Solve with iterative quickselect, a random pivot and a three-way partition; example inputs ([3,2,1,5,6,4], 2) and ([3,2,3,1,2,4,5,5,6], 4)
Include sorted-input and all-duplicate tests of 100,000 elements before submitting. After submitting, read the AlgoMaster write-up for Kth Largest Element in an Array (https://algomaster.io/learn/dsa/kth-largest-element-in-an-array).
LeetCode 347: Top K Frequent Elements
Hash the counts first, then select top \(k\); example inputs ([1,1,1,2,2,3], 2) and ([1], 1)
Solve it twice: once with a size-k heap, once with quickselect on (count, value) pairs, and state which you would ship for a stream. After submitting, read the AlgoMaster write-up for Top K Frequent Elements (https://algomaster.io/learn/dsa/top-k-frequent-elements).
Self-test
-
State the Lomuto invariant and what the final swap establishes.
During the scan,arr[lo..i]holds elements <= pivot,arr[i+1..j-1]holds elements > pivot, andarr[j..hi-1]is unexamined. The final swap moves the pivot just past the<=band, so it sits at its final sorted index with everything left <= it and everything right > it. -
Why does Lomuto with a random pivot still go quadratic on all-equal input, and what fixes it?
Every key equal to the pivot lands on one side (left with<=, right with<), so each partition removes only the pivot and \(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\). Three-way partition groups all pivot-equal keys in one pass, so the recursion skips them and the cost is \(\Theta(n)\). -
When does a size-k heap beat quickselect for top-k, and when does it lose asymptotically?
The heap wins when the input streams (quickselect needs random access to the whole array) or when \(O(k)\) space without mutation matters. At \(k = n/2\) the heap costs \(O(n \log n)\) and loses its edge while quickselect stays expected \(O(n)\). Sorted output adds \(O(k \log k)\) on top of either. -
What does introselect change about quickselect's worst case?
It watches the recursion depth and switches to a guaranteed method past about \(2 \lg n\) levels: median-of-medians in Musser's design, which keeps the worst case linear, or heap selection in libstdc++'snth_element, which caps it at \(O(n \log n)\). The median-of-medians proof belongs to algorithms/decomposition-greedy-randomness/divide-conquer-recurrences.
Completion criterion
Stop when
Your quickselect returns 5 on the handbook example, survives sorted and all-equal inputs, passes 300 differential cases, and you can route a new top-k task to heap, quickselect or full sort from its streaming and output constraints.
Mark passed, then open 2.3 Only mark this when you can do it without notes.Leads to
- 4.2 Divide and conquer, recurrences and partition-based selection Recurrence analysis and deterministic median-of-medians live there; this unit uses only the random-pivot form.
- 4.5 Randomized correctness, expected cost and selection Expected-cost analysis of random pivots lives there.
- 2.6 Heaps and priority queues The heap side of the top-k trade-off.
Comes after
- 2.1 Sorting contracts, lower bounds and merge sortPartition-based sorting and selection continue the comparison-sort story.
- 2.6 Heaps and priority queuesReturn there for the top-k routing decision between heaps and quickselect.
- 4.2 Divide and conquer, recurrences and partition-based selectionPartition invariant, quickselect implementation, adversarial pivots, and heap versus quickselect versus full sort.
- 4.5 Randomized correctness, expected cost and selectionThe partition invariant this analysis assumes.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.