Quickselect
The Intuition
Sorting an array gives you every rank at once. If the question only asks for one rank, sorting is overkill. Quickselect is a partition-based algorithm that delivers a single rank in O(n) average time without producing the rest of the sorted order.
The pattern reuses the partition step from quicksort. After one partition, the pivot lands at its final sorted position p. Everything left of p is smaller, everything right is larger. Compare p to the target rank k. If they match, the pivot is the answer. If p is smaller than k, the answer lives in the right half and the left half is irrelevant. If p is larger, recurse left.
Because each step throws away one side, the work series is n + n/2 + n/4 + ... which sums to 2n, giving O(n) average. The worst case is O(n^2) on adversarial pivots, prevented in practice by choosing the pivot uniformly at random or via median-of-three.
This pattern beats heap-top-k whenever the array is already in memory and you have permission to permute it. A min-heap of size k for top-k is O(n log k), which is asymptotically slower for large n. Heap wins when input arrives as a stream and you cannot store all of it.
The pattern generalizes: anywhere you need "the value at rank k" or "the k-smallest values, order-irrelevant", quickselect fits. After the call, the array is partitioned around the answer, so reading indices [0..k-1] gives the k smallest unordered.
kth smallest or largest in an array, median of an unsorted list, top-k with no order required, partition-based selection problems.
- Streaming or unbounded input (use a heap)
- The array is read-only and copying is too expensive
- You need every rank sorted (just sort)
- Input size is so small that the constant factor of sort wins
Variations:
- Top-K unordered: Run quickselect to position k, then return the first k elements as an unordered set in O(n).
- Wiggle sort and Dutch flag: Three-way partition extends quickselect to multi-pivot grouping in one pass.
- Median of medians: Deterministic O(n) worst case by choosing the pivot as the median of group medians. Heavier constant; rarely beats randomized in practice.
- single element
- all elements equal (three-way partition avoids quadratic behavior)
- k out of bounds (validate before recursing)
Key Points
- •Partition like quicksort, then recurse only on the side that contains the target rank
- •Average work shrinks geometrically (n + n/2 + n/4 ...) which sums to O(n)
- •Random or median-of-three pivot avoids the O(n^2) worst case on adversarial input
- •Returns the value at a target rank without sorting the rest of the array
- •Trades stability and "all sorted" output for a faster single-rank answer
Code Template
1 import random
2
3 def quickselect(nums, k):
4 """Return the kth smallest element (1-indexed) in-place via partitioning."""
5 a = nums[:]
6 lo, hi, target = 0, len(a) - 1, k - 1
7 while lo <= hi:
8 p = partition(a, lo, hi)
9 if p == target:
10 return a[p]
11 if p < target:
12 lo = p + 1
13 else:
14 hi = p - 1
15 return -1
16
17 def partition(a, lo, hi):
18 # Random pivot avoids worst case on sorted input.
19 pivot_idx = random.randint(lo, hi)
20 a[pivot_idx], a[hi] = a[hi], a[pivot_idx]
21 pivot, store = a[hi], lo
22 for i in range(lo, hi):
23 if a[i] < pivot:
24 a[i], a[store] = a[store], a[i]
25 store += 1
26 a[store], a[hi] = a[hi], a[store]
27 return store
28
29 def kth_largest(nums, k):
30 """Wrapper: kth largest is the (n - k + 1)th smallest."""
31 return quickselect(nums, len(nums) - k + 1)Common Mistakes
- Using the first or last element as the pivot on already-sorted input (O(n^2))
- Off-by-one between 0-indexed rank k and 1-indexed kth-smallest
- Forgetting to swap pivot back into place after partitioning
- Recursing on both sides (that is sort, not select)