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.
Where it lands in Jayverse
- Verex: use introselect for p99 fill-price/gas-price monitoring. Compute the CLOB's live p99 fill-price and gas-price metrics with quickselect/introselect instead of sorting, and add a test with sorted or all-equal input to catch the quadratic worst case the page warns about.
- gitboard: switch p99 latency to selection once volume grows. Any p99 gitboard displays should move from full sort to selection at scale, with the median-of-medians fallback as the guard if quickselect ever gets gamed by adversarial input.
- Number: standardize an introselect-based utility for rolling quantiles. For indicator research needing rolling medians or quantiles over large series, use one shared selection-based utility instead of ad hoc sorting, to keep large backtests linear.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| recurse into | 재귀적으로 ~쪽으로 파고들다 · "only recurses into the side that contains the pivot" |
| degrade to | (성능이) ~수준으로 떨어지다 · "degrade it to quadratic time" |
| fall back to | 안 되면 ~으로 대체 수단을 쓰다 · "fall back to the deterministic median-of-medians selection" |
| dragged into | (원치 않게) ~상태로 끌려가다 · "dragged into its worst case by adversarial input" |
| pay an unnecessary tax | 불필요한 비용 부담을 치르다 · "pays an unnecessary log-factor tax" |
| eliminate at every step | 매 단계마다 제거하다 · "a fixed fraction of elements is eliminated at every step" |
| state an explicit bound | 명시적인 한계치를 제시하다 · "state an explicit worst-case time bound" |
| order statistic | 순서통계량(order statistic) · 배열을 정렬했을 때 k번째로 작은 원소를 가리키는 용어. "the k-th smallest element an array would have" |
| introselect | 인트로셀렉트(introselect) · Quickselect로 시작해 재귀 깊이가 임계값을 넘으면 median-of-medians로 전환하는 하이브리드 선택 알고리즘. "the introselect pattern" |
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/.