Quickselect & partition
📖 Walk me through it — plain English
Sometimes you do not need the whole array sorted — you just want one ranked value, like "the 3rd smallest number" or "the median." Sorting everything to learn the position of a single value is wasteful. Quickselect finds that one value directly, and on average it does it in linear time — roughly one pass-worth of work, written O(n), where n is the number of elements.
The engine is a step called partition. You pick one element to be the pivot (a reference value). Then you shuffle the array in place so every element smaller than the pivot ends up to its left and every larger element ends up to its right. After that shuffle the pivot is sitting in the exact slot it would occupy if the whole array were sorted — call that index p. We never had to sort anything else to know p is the pivot's true rank.
Here is the clever part, and the reason this is faster than sorting. We are hunting for the element at rank k (0-indexed: k=0 means the smallest). After partitioning we compare p to k. If p == k, the pivot is our answer — done. If the pivot landed too far left (p < k), our target must be further right, so we throw away the entire left side and repeat on the right. If it landed too far right, we keep only the left. Each round we discard a whole chunk we never look at again.
Analogy: imagine a phone book and you want the 200th name. You flip to a random page, glance at the name, and ask "is the 200th before or after here?" Whatever half it is not in, you slam shut and ignore. Each glance throws away a pile of pages you never reopen — that is exactly what discarding a side does here.
Let's trace "find the 3rd smallest of [3,2,1,5,4]." 3rd smallest is rank k=2 (0-indexed). To keep the trace reproducible we'll always use the last element as the pivot.
The 3rd smallest is 3 — and notice we never fully sorted the array. Why is it fast? Each partition costs work proportional to the slice it scans, but then we drop one side and recurse only on the other. On average the survivor is about half, so the total work is n + n/2 + n/4 + … ≈ 2n, which is O(n) — beating the O(n log n) of a full sort. The catch: if you always pick a terrible pivot (the min or max every time), nothing gets discarded and it degrades to O(n^2). That is why the real code picks a random pivot — so a sorted or adversarial input cannot reliably trigger the slow case.
When you only need the kth smallest (or largest) element, sorting the whole array is overkill — you are paying O(n log n) to learn the position of one value. Quickselect borrows the partition step from quicksort: pick a pivot, rearrange the array so everything smaller sits left of it and everything larger sits right, and the pivot lands in its final sorted position p. Now the trick — unlike quicksort, you do not recurse into both halves. If p == k you are done; if p < k the answer is strictly to the right, so you throw the entire left side away; otherwise you keep only the left. Each step discards a chunk you never revisit. On average the survivor is about half the array, so the work is n + n/2 + n/4 + … ≈ 2n — a geometric series that sums to O(n). The concrete anchor: "3rd smallest of [3,2,1,5,4]" partitions to [3,2,1,4,5], sees the pivot land at index 3, decides the rank-2 target is to its left, and recurses only there.
- "kth largest" or "kth smallest element"
- "Top K" where order within the K does not matter
- The median, or any percentile, of an unsorted array
- You need one ranked value, not a full ordering
- Quickselect: avg O(n), in place, one-shot query
- Min/max heap of size k: O(n log k), great for streaming
- Full sort: O(n log n) — only if you need everything ordered
- Need order inside the K too? A heap keeps it; quickselect does not
import random
def kth_smallest(arr, k): # k is 0-indexed: k=0 -> min
lo, hi = 0, len(arr) - 1
while True:
p = partition(arr, lo, hi)
if p == k: return arr[k]
elif p < k: lo = p + 1 # target is to the right
else: hi = p - 1 # target is to the left
def partition(arr, lo, hi):
r = random.randint(lo, hi) # random pivot dodges sorted-input O(n^2)
arr[r], arr[hi] = arr[hi], arr[r] # park pivot at the end
pivot, i = arr[hi], lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i] # pivot into its final slot
return i
# kth LARGEST -> kth_smallest(arr, len(arr) - k) with k 1-indexedfunction kthSmallest(arr: number[], k: number): number {
let lo = 0, hi = arr.length - 1; // k is 0-indexed
while (true) {
const p = partition(arr, lo, hi);
if (p === k) return arr[k];
else if (p < k) lo = p + 1;
else hi = p - 1;
}
}
function partition(arr: number[], lo: number, hi: number): number {
const r = lo + Math.floor(Math.random() * (hi - lo + 1));
[arr[r], arr[hi]] = [arr[hi], arr[r]]; // random pivot -> park at end
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; }
}
[arr[i], arr[hi]] = [arr[hi], arr[i]];
return i;
}- Average O(n): the discarded side shrinks the problem geometrically, n + n/2 + n/4 + … ≈ 2n. Worst O(n^2) when every pivot is the min/max (already-sorted input with a fixed end pivot).
- Pick a random pivot (or median-of-three) so an adversarial / sorted array cannot force the quadratic case — this is the single most important guard.
- Convert kth-largest to an index: the kth largest is the (n - k)th smallest (0-indexed). Off-by-one here is the most common bug — decide 0- vs 1-indexed up front.
- Equal elements degrade two-way Lomuto when many keys match the pivot; switch to a 3-way partition (Dutch-national-flag: <, ==, >) to skip the equal band entirely.
- In place, O(1) extra space. The loop form above also avoids recursion stack — Lomuto returns the final pivot index, never both sides.
- It is unstable and it mutates the input; copy first if the caller still needs the original order.
Find the kth smallest with quickselect — partition and recurse: