Quickselect

Find the k-th smallest in O(n) — without sorting. Quicksort's partition, recursing into ONE side.

One change from quicksort

• Partition around a pivot → pivot lands at rank p
• p == k → done. k < p → recurse left. k > p → recurse right.
• Ignore the side that can't contain rank k
• n + n/2 + n/4 + … = 2n → O(n) average

Watch it narrow to rank k

Pink = target rank. Dark = discarded regions. Each partition throws away a whole side.

O(n) select vs O(n log n) sort

Quickselect ~ties C sort (Python handicap). heapq for the median: 6× worse — wrong k.

Match the tool to k

• Small k (top-10) → heapq.nsmallest (O(n log k))
• Median / arbitrary rank → quickselect (O(n))
• Many ranks / full order → just sort
• Randomize the pivot (O(n²) worst case, like quicksort)

Takeaway

Compute just enough order to place one element. Median-of-medians guarantees linear worst case. Next tier: trees.