Randomized Quickselect

🔥 Vibe Prompt

"Find the median of 10M numbers using Quickselect. Show expected vs worst-case time."

import random

def quickselect(arr, k):
    """Return k-th smallest (0-indexed)"""
    if len(arr) == 1:
        return arr[0]
    
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    if k < len(left):
        return quickselect(left, k)
    elif k < len(left) + len(mid):
        return mid[0]
    else:
        return quickselect(right, k - len(left) - len(mid))

# Test
import time
data = [random.randint(0, 1000000) for _ in range(100000)]

# Random pivot
start = time.time()
med = quickselect(data, len(data)//2)
time_rand = time.time() - start

# Deterministic (min element for worst case)
def quickselect_worst(arr, k):
    pivot = min(arr)  # Always worst-case
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    if k < len(left): return quickselect_worst(left, k)
    elif k < len(left) + len(mid): return mid[0]
    else: return quickselect_worst(right, k - len(left) - len(mid))

print(f"Median: {med}")
print(f"Random pivot: {time_rand*1000:.2f}ms (expected O(n))")
print(f"\nRandomized avoids O(n²) worst-case!")

Why Randomize?

| Approach | Best | Average | Worst | |----------|------|---------|-------| | Deterministic | O(n) | O(n) | O(n²) | | Randomized | O(n) | O(n) | O(n) (prob.) |

Applications

Real-time median calculation
Order statistics in DB
Load balancing
Outlier detection

Key Points

Understand the core concepts thoroughly
Practice with hands-on code examples
Apply knowledge to real-world problems
Review and reinforce through exercises

Further Learning

Official documentation
Open source projects on GitHub
Community forums and discussions
Related courses and tutorials

為什麼你需要學會第 k 小元素的快速選擇？

想像你正在開發一個即時分析系統，每天從 1000 萬筆交易中找到中位數價格——不是全部排序，只要中位數。

全部排序（O(n log n)）：1000 萬 × log(1000 萬) ≈ 2.3 億次比較，約需 5 秒
Quickselect（期望 O(n)）：約 1000 萬次比較，約需 0.02 秒——快 250 倍

不只是中位數——找第 95 百分位數（效能監控的 P95 延遲）、找前 10 名、找面試中的第 k 大元素——Quickselect 都是你該選的工具。

為什麼隨機化這麼重要？

如果不隨機化，選第一個元素作為 pivot，那在已排序的陣列上，Quickselect 會退化到 O(n²)——每次只能排除一個元素。

隨機 pivot 保證了期望 O(n)——不管輸入是什麼，演算法的平均表現都是一樣的。這就是隨機化演算法最強大的特性：不受對手（惡意輸入）影響。

固定 pivot（第一個元素）
已排序輸入 [1,2,3,...,1000] → 每次排除 1 個 → O(n²)

隨機 pivot
任意輸入 → 每次期望排除 n/2 個 → O(n)

下一章預告：從選取到抽樣

Quickselect 解決的是「在已知的陣列中找到第 k 小的元素」。但如果你遇到的資料不是一個已知大小的陣列，而是一個不知道有多大的串流呢？

下一章 水庫抽樣 (Reservoir Sampling) 解決的正是這個問題——從一個未知大小的串流中，均勻隨機地抽出 k 個樣本。