Quickselect & Order Statistics
In short: finding the kth smallest item does not need a full sort. Quick
sort's partition step (section 3) already tells you exactly where one item —
the pivot — belongs in sorted order. If that spot is k, you're done. If
it's past k, the answer is somewhere in the left part; if it's before k, the
answer is in the right part. Either way, only one side ever gets
partitioned again — the other is thrown away, unsorted, forever. That turns
an O(n log n) sort into an O(n) average-case selection, because the work per
round shrinks geometrically: roughly n + n/2 + n/4 + …, which sums to about
2n.
Find the median latency without sorting the log
Quarry's dashboard needs the median response time from a batch of requests, refreshed constantly. Sorting the whole log every refresh is wasted work — the median is just one or two positions, found with quickselect:
Watch quickselect hunt for the 3rd smallest of six values, discarding a side every round instead of sorting all six:
Every round partitions around one pivot and keeps only the side that can still hold the target rank. The other side is never looked at again.
Finding the 3rd smallest (target index 2). Pivot on the last value, 15. 6 cells. At index 5.
Why the discarded side really is safe to forget
The partition's one guarantee is: every value before the pivot's final index is less than the pivot, and every value after is greater than or equal to it. If the target rank falls after the pivot's index, nothing in the left part — all smaller than the pivot, hence smaller than the target — can possibly be the answer, so there is nothing left to check there:
def quickselect(items, target, lo, hi):
while True:
pivot = items[hi]
i = lo
for j in range(lo, hi):
if items[j] < pivot:
items[i], items[j] = items[j], items[i]
i += 1
items[i], items[hi] = items[hi], items[i]
if i == target:
return items[i]
if i < target:
lo = i + 1
else:
hi = i - 1
print(quickselect([5, 2, 8, 1, 9, 3], 0, 0, 5))Full sort vs. quickselect: same worst case, different average
Both quick sort and quickselect can degrade to O(n²) if every pivot is the smallest or largest remaining value — but quickselect's average case is O(n), not O(n log n), because it only ever recurses into one side:
IndexErrorThis crashes instead of returning the 3rd smallest. The two branches of the if are swapped.
Quick practice
def quickselect(items, target, lo, hi):
while True:
pivot = items[hi]
i = lo
for j in range(lo, hi):
if items[j] < pivot:
items[i], items[j] = items[j], items[i]
i += 1
items[i], items[hi] = items[hi], items[i]
if i == target:
return items[i]
if i < target:
lo = i + 1
else:
hi = i - 1
print(quickselect([9, 1, 8, 2, 7], 4, 0, 4))n = 100_000
rounds_work = n
total = n
while rounds_work > 1:
rounds_work //= 2
total += rounds_work
print(total < 2 * n)🎯 Your turn
Build median_latency(latencies): return the median of latencies as a
float, using quickselect — no sorted(). Odd length: the single middle
value. Even length: the average of the two middle values.
median_latency([120, 80, 95, 300, 60])→95.0median_latency([120, 80, 95, 300])→107.5
Hint: write quickselect(items, target, lo, hi) once (Lomuto partition
on items[hi]), then call it with target = n // 2 for odd n, or twice —
n // 2 - 1 and n // 2 — for even n, averaging the results.
Press ▶ Run, try the Live App chips, then ✓ Check.