Quickselect & Partitioning
Find the k-th smallest element in O(n) average time using quicksort's partition step - without fully sorting.
On this page
To find the k-th smallest element, sorting works (O(n log n)) and a heap works (O(n log k)). But there's a faster average approach that finds it in O(n) without sorting at all: quickselect, built on quicksort's partition step. It's a favorite interview question precisely because it shows you understand partitioning.
Partition: the heart of quicksort
Partitioning rearranges an array around a pivot so that everything smaller is on its left and everything larger on its right. After partitioning, the pivot is in its final sorted position - even though the rest isn't sorted:
// Lomuto partition: place pivot (last element) in its sorted spot, return its index
int partition(int[] a, int lo, int hi) {
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) swap(a, i++, j); // push smaller elements left
swap(a, i, hi); // pivot into place
return i; // pivot's final index
}Quickselect: recurse into only one side
Here's the insight: after a partition, if the pivot lands at index p, then p is the pivot's rank. If
you want the k-th smallest and p == k, you're done. If k < p, the answer is in the left part; if
k > p, the right. Unlike quicksort, you recurse into only one side - which is what makes it
O(n) average:
// k-th smallest (0-indexed) — O(n) average, O(n^2) worst
int quickselect(int[] a, int k) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int p = partition(a, lo, hi);
if (p == k) return a[p];
if (p < k) lo = p + 1; // answer is to the right
else hi = p - 1; // answer is to the left
}
return -1;
}Because each step discards one side, the average work is n + n/2 + n/4 + … ≈ 2n = O(n) - versus
quicksort's O(n log n), which must sort both sides. The worst case is O(n²) with unlucky pivots
(mitigated by random pivot selection).
Three ways to find the k-th smallest
Know all three and their trade-offs: sorting is O(n log n) and simplest; a size-k heap is O(n log k) and works on streams; quickselect is O(n) average, in place, best when you have the whole array and want one order statistic. Interviewers love asking you to compare them.
To find the median-height person in a crowd, you don't need everyone in a perfect height line (a full sort). Pick someone at random and ask everyone shorter to step left, taller to step right - now you know that person's exact rank without sorting either group. If their rank is past the median, the median is among the 'shorter' group, so you repeat the process on just that group, ignoring the other half entirely. Each round throws away half the crowd, so you home in on the median after examining roughly 2n people total - far less work than lining up all n.
You need the k-th largest element of a large array you fully control (not a stream). Compare quickselect against the size-k heap approach in time complexity, and say when each is the better choice.
Why is quickselect O(n) on average while quicksort is O(n log n)?
Key takeaways
- Partitioning places a pivot in its final sorted position with smaller elements left, larger right - the core of quicksort.
- Quickselect finds the k-th smallest in O(n) average by partitioning and recursing into only the side containing the answer.
- It's faster than sorting (O(n log n)) or a heap (O(n log k)) for a one-shot order statistic on an in-memory array.
- Worst case is O(n^2) with bad pivots; random pivot selection makes that vanishingly unlikely.
- Choose by context: sorting (simplest), size-k heap (streams/top-k over time), quickselect (one order statistic, in place).