Sorting & Searching
Order Statistics & Selection
Finding the k-th smallest element doesn't require sorting the whole array — quickselect answers it in expected O(n) by reusing quicksort's partition and discarding the half that can't contain the answer.
- Quickselect: partition like Quicksort, then recurse into only the side that contains the k-th index
- Expected O(n) — each partition eliminates a constant fraction of the remaining elements, giving a geometric series that sums to O(n), not O(n log n)
- Worst case O(n²) with a bad pivot, same failure mode as quicksort — randomization fixes it the same way
- Median-of-medians selection guarantees worst-case O(n) but with a large constant factor, so it's a theoretical result more than a practical default
- For a stream or when k is small and fixed, a size-k heap (Heap Top K Pattern) is simpler and often preferred
static int quickselect(int[] a, int lo, int hi, int k) { // k is 0-indexed
if (lo == hi) return a[lo];
int p = partition(a, lo, hi); // same partition as quicksort
if (k == p) return a[k];
if (k < p) return quickselect(a, lo, p - 1, k);
return quickselect(a, p + 1, hi, k);
}| Approach | Time | When to prefer it |
|---|---|---|
| Sort then index | O(n log n) | need the full order anyway, or k varies repeatedly |
| Quickselect | O(n) expected, O(n²) worst | one-shot query, array fits in memory |
| Size-k heap | O(n log k) | streaming input, or k ≪ n |