一句話解釋

隨機選 pivot 讓 Quicksort 期望 O(n log n)，避免 worst-case O(n²)；隨機選擇演算法期望 O(n) 找第 k 小。

Randomized QuickSort

演算法設計

確定性 Quicksort 的問題

Worst-case： $O(n^2)$

  • 每次 pivot 都是最小/最大值
  • 例如已排序陣列 + 總是選第一個元素

問題： 對手（adversary）可以構造最壞輸入

隨機化解法

Algorithm: Randomized QuickSort
Input: 陣列 $A[1..n]$
Output: 排序後的陣列
  1. **If** $n \leq 1$: **Return** $A$
  2. **隨機均勻**選擇 pivot $p \in A$
  3. 分割（Partition）：
    • $L = \{x \in A : x < p\}$
    • $M = \{x \in A : x = p\}$
    • $R = \{x \in A : x > p\}$
  4. 遞迴排序 $L$ 和 $R$
  5. **Return** QuickSort$(L)$ + $M$ + QuickSort$(R)$
def randomized_quicksort(A): if len(A) <= 1: return A pivot = random.choice(A) # 隨機選 pivot L = [x for x in A if x < pivot] M = [x for x in A if x == pivot] R = [x for x in A if x > pivot] return randomized_quicksort(L) + M + randomized_quicksort(R)

關鍵觀察

  • 隨機性在演算法內部，不依賴輸入分佈
  • 任何輸入的期望時間都是 $O(n \log n)$
  • Worst-case 仍是 $O(n^2)$，但機率極小

期望時間分析

比較次數

分析策略

關鍵： 分析比較次數（dominate 運行時間）

設定

排序後陣列為 $z_1 \leq z_2 \leq \cdots \leq z_n$。

定義指示變數：

$$ X_{ij} = \begin{cases} 1 & \text{若 } z_i \text{ 和 } z_j \text{ 有被比較} \\ 0 & \text{否則} \end{cases} $$ 總比較次數： $$ X = \sum_{i=1}^{n-1} \sum_{j=i+1}^n X_{ij} $$

期望值計算

用 **Linearity of Expectation**： $$ \mathbb{E}[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \mathbb{E}[X_{ij}] = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \Pr[z_i \text{ 和 } z_j \text{ 比較}] $$

關鍵引理

Lemma: $$\Pr[z_i \text{ 和 } z_j \text{ 比較}] = \frac{2}{j - i + 1}$$ 證明思路： $z_i$ 和 $z_j$ 會比較，若且唯若： - 在 $\{z_i, z_{i+1}, \dots, z_j\}$ 中，**第一個被選為 pivot 的是 $z_i$ 或 $z_j$** 原因： - 若先選中間某個 $z_k$（$i < k < j$），則 $z_i$ 和 $z_j$ 被分到不同子陣列，永不比較 - 若先選 $z_i$ 或 $z_j$，它們會在 partition 時比較 機率： 在 $\{z_i, \dots, z_j\}$ 共 $j-i+1$ 個元素中，隨機選一個作為第一個 pivot： $$ \Pr[\text{選到 } z_i \text{ 或 } z_j] = \frac{2}{j-i+1} $$

最終計算

$$ \begin{align} \mathbb{E}[X] &= \sum_{i=1}^{n-1} \sum_{j=i+1}^n \frac{2}{j-i+1} \\ &= \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} \frac{2}{k} \quad (\text{令 } k = j-i+1) \\ &\leq \sum_{i=1}^{n-1} \sum_{k=2}^{n} \frac{2}{k} \\ &= (n-1) \cdot 2 \sum_{k=2}^{n} \frac{1}{k} \\ &= (n-1) \cdot 2 (H_n - 1) \\ &= O(n \log n) \end{align} $$ 其中 $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n} = \Theta(\log n)$ 是調和級數。

🎯 結論：
Randomized QuickSort 的期望比較次數是 $O(n \log n)$，對任何輸入都成立！

Randomized Selection（第 k 小）

QuickSelect

問題

輸入： 陣列 $A[1..n]$，整數 $k \in [1, n]$
輸出： 第 $k$ 小的元素

演算法

Algorithm: Randomized Select
  1. 隨機選 pivot $p \in A$
  2. 分割成 $L, M, R$（同 QuickSort）
  3. **If** $k \leq |L|$: **Return** Select$(L, k)$
  4. **Else If** $k \leq |L| + |M|$: **Return** $p$
  5. **Else**: **Return** Select$(R, k - |L| - |M|)$
def randomized_select(A, k): if len(A) == 1: return A[0] pivot = random.choice(A) L = [x for x in A if x < pivot] M = [x for x in A if x == pivot] R = [x for x in A if x > pivot] if k <= len(L): return randomized_select(L, k) elif k <= len(L) + len(M): return pivot else: return randomized_select(R, k - len(L) - len(M))

關鍵差異

  • QuickSort：遞迴兩邊
  • QuickSelect：只遞迴一邊（包含第 $k$ 小的那邊）

QuickSelect 期望分析

期望時間

遞迴關係

令 $T(n)$ 是期望運行時間。

Partition 的期望行為： 假設 pivot 落在排序後的第 $i$ 位置（$1 \leq i \leq n$），機率 $\frac{1}{n}$。 - 若 $k \leq i$：遞迴到 $L$，大小 $\leq i-1$ - 若 $k > i$：遞迴到 $R$，大小 $\leq n-i$ 遞迴式： $$ T(n) \leq \frac{1}{n} \sum_{i=1}^{n} \left[ O(n) + T(\max(i-1, n-i)) \right] $$

簡化分析

定義「好的 pivot」： pivot 落在中間 50%（第 $n/4$ 到第 $3n/4$ 位）。 機率：$\frac{1}{2}$ 好的 pivot → 問題大小縮小到 $\leq \frac{3n}{4}$ 期望步數直到好的 pivot： 2 次 期望總時間： $$ T(n) \leq 2 \cdot O(n) + T(3n/4) = O(n) + T(3n/4) $$ 展開： $$ \begin{align} T(n) &\leq cn + T(3n/4) \\ &\leq cn + c(3n/4) + T((3/4)^2 n) \\ &\leq cn \sum_{i=0}^\infty (3/4)^i = cn \cdot \frac{1}{1 - 3/4} = 4cn = O(n) \end{align} $$

🎯 結論：
Randomized Select 的期望時間是 $O(n)$，線性時間找第 k 小！

與確定性演算法比較

確定性 Median-of-Medians 演算法：

  • Worst-case $O(n)$
  • 但常數很大，實務上較慢

Randomized Select：

  • 期望 $O(n)$，worst-case $O(n^2)$（機率極小）
  • 簡單實作，實務上很快

實務考量

Hybrid 策略

實務中常用的優化：

  1. 小陣列用 Insertion Sort（$n \leq 10$）
  2. Median-of-3： 選三個元素的中位數作 pivot（降低壞 pivot 機率）
  3. 三分法： 分成 $< p$, $= p$, $> p$ 處理重複元素

Python 的 sorted()

CPython 使用 Timsort（基於 Merge Sort + Insertion Sort），不是 Quicksort。

原因：

  • Stable（穩定排序）
  • 對部分排序資料很快
  • Worst-case $O(n \log n)$（Quicksort 是期望）

但很多語言（C++ std::sort, Java）用混合的 Quicksort。

總結

Randomized Sorting & Selection 是隨機演算法的經典應用：

  1. Randomized QuickSort：
    • 期望 $O(n \log n)$ 比較
    • 簡單、實用、快速
    • 分析用 Linearity of Expectation
  2. Randomized Select：
    • 期望 $O(n)$ 找第 $k$ 小
    • 比確定性演算法簡單得多
    • 關鍵：只遞迴一邊
  3. 分析技巧：
    • 指示變數 + Linearity
    • 「好的 pivot」機率分析
    • 幾何級數求和

參考資料

  • CLRS, Introduction to Algorithms, Chapter 7 & 9
  • Motwani & Raghavan, Randomized Algorithms, Chapter 1
  • Hoare, “Quicksort” (1961)