Order Statistics TODO
Concept
An order statistic is the k-th smallest element an array would have if sorted, and the problem of finding just that element without sorting everything is called the selection problem. Quickselect reuses quicksort's partition step but only recurses into the side that contains the pivot, giving expected linear time — though a consistently bad pivot choice can degrade it to quadratic time in the worst case. Median-of-medians groups elements into blocks of 5, takes the median of each group, and then uses the median of those medians as the pivot, which guarantees that a fixed fraction of elements is eliminated at every step. That guarantee makes the recurrence solve to linear time even in the worst case, but the constant factor is large enough that it's slow in practice. So real implementations typically start with Quickselect and fall back to the deterministic median-of-medians selection once recursion depth crosses a threshold — the introselect pattern.
When you're computing p99 latency or pulling the top N items, sorting the entire array pays an unnecessary log-factor tax, while a naive Quickselect can be dragged into its worst case by adversarial input.
Code & Formula
# Day 8: 순서 통계 — Quickselect로 k번째로 작은 원소를 전체 정렬 없이 찾기
# 퀵정렬의 분할을 재사용하되 필요한 한쪽 구간만 재귀해 기대 O(n) 시간에 선택한다.
import random
def quickselect(arr, k):
"""arr에서 k번째로 작은 원소(0-indexed)를 반환."""
arr = arr[:]
lo, hi = 0, len(arr) - 1
while True:
if lo == hi:
return arr[lo]
pivot = arr[random.randint(lo, hi)]
lt, gt, i = lo, hi, lo
while i <= gt:
if arr[i] < pivot:
arr[i], arr[lt] = arr[lt], arr[i]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
if k < lt:
hi = lt - 1
elif k > gt:
lo = gt + 1
else:
return pivot
random.seed(3)
data = [random.randint(0, 1000) for _ in range(1000)]
k = 500
result = quickselect(data, k)
expected = sorted(data)[k]
print(f"데이터 {len(data)}개 중 {k}번째(0-indexed)로 작은 값 = {result}")
print(f"sorted()로 검증한 값 = {expected}, 일치 = {result == expected}")
docs/code/algorithms/algorithms-8.py
Exercise
Implement Quickselect to find the k-th element of an integer array, then count comparisons on a sorted input and an all-equal-values input, and plot those against a random-pivot version.
Practical Connection
Whether you're computing the median or a quantile of gas prices or order-book fill prices on-chain or off-chain, using a selection algorithm instead of sorting cuts the work and lets you state an explicit worst-case time bound against adversarial input.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.