線性時間排序演算法

Counting Sort

Counting Sort 分析

Proof

• 符號 \(A[1..n]\) 輸入，每個鍵在 \(0..k\); \(B[1..n]\) 輸出; \(C[0..k]\) 計數。

• 步驟

  1. 初始化：對 \(i=0..k\)，令 \(C[i]=0\)。

  2. 計數：掃描 \(A\)，對 \(x=A[j]\) 執行 \(C[x] \leftarrow C[x]+1\)。完成後 \(C[i]\) 為「值等於 \(i\) 的個數」。

  3. 前綴和：對 \(i=1..k\)，令 \(C[i] \leftarrow C[i]+C[i-1]\)

  4. 回填（由右往左）：對 \(j=n..1\)，令 \(x=A[j]\)，設 \(B[C[x]]\leftarrow x\)，再令 \(C[x]\leftarrow C[x]-1\)。

• 正確性

  • 由上式，\(C[i]\) 是「\(\le i\) 的元素個數」。因此值為 \(i\) 的元素應被放入區間 \((C[i-1]+1)..C[i]\)。

  • 在第 4 步中，\(j\) 自右往左處理並遞減 \(C[i]\)，恰好把所有值為 \(i\) 的元素依序填入該區間，且保持原相對次序（穩定）。

• 時間

  • 初始化：\(k+1\) 次賦值 ⇒ \(\Theta(k)\)。

  • 計數：掃一次 \(A\) ⇒ \(\Theta(n)\)。

  • 前綴和：掃一次 \(C\) ⇒ \(\Theta(k)\)。

  • 回填：掃一次 \(A\) ⇒ \(\Theta(n)\)。

  • 合併： \(\Theta(k)+\Theta(n)+\Theta(k)+\Theta(n)=\Theta(n+k)\)

  • 那為什麼是 linear time 是因為可以使用兩個角度看

    1. 若 \(k\) 的值域也是成 linear 分佈 \(O(n)\)，那麼 \(O(n+k) \Rightarrow O(n+O(n))\)

    2. 也可以把 \(k\) 的值域限制在 \(0\)~\(k\) 之間那麼可以把 \(k\) 看成常數那麼 \(O(n+k)=O(n+c)\)

• 空間 額外需要 \(B[1..n]\) 與 \(C[0..k]\)，故為 \(\Theta(n+k)\)

• 備註 非比較式排序，故不受比較模型的 \(\Omega(n\log n)\) 下界限制。

Radix Sort (CLRS) or LSD Radix Sort (DS)

核心概念

• 非比較式排序；以「位數」為鍵，由最低位→最高位依序處理（LSD）。

• 每回合使用穩定子排序（常用 Counting Sort），或是可以使用 Bubble 或是 Insertion。

• 流程：按當前位分桶 \(0..r-1\) → 依 \(0..r-1\)、以 FIFO 合併回陣列。

• 不變量：處理到位 pos 後，最低 pos+1 位已有序；下一回合不破壞既有次序。

• 前提：每個鍵可表示為 d 位、基底 r（每位範圍 \(0..r-1\)）。

• 複雜度：子排序若為 \(\Theta(n+r)\)，則總成本 \(\Theta\big(d(n+r)\big)\)；空間視桶與子排序而定。

操作方式

• distribution：依據個資料的位數數值，分派到對應的桶子中。

• merge：依據桶子的編號 \(0 \rightarrow (r-1)\) 桶子裡面把資料 merge 然後變成下一回合的輸出

LSD Radix Sort — 虛擬碼（Pseudocode）

RADIX-SORT-LSD(A, n, d, r):
  # A[1..n]，每個鍵有 d 位，基底 r（每位 0..r-1）
  for pos ← 0 to d-1:                 # 0=最低位
    STABLE-COUNTING-SORT-BY-DIGIT(A, n, pos, r)

STABLE-COUNTING-SORT-BY-DIGIT(A, n, pos, r):
  # 以第 pos 位作穩定計數排序；輸出回寫到 A（可用輔助陣列 B）
  create array C[0..r-1] ← 0
  create array B[1..n]

  # 計數
  for j ← 1 to n:
    d ← DIGIT(A[j], pos, r)           # 取第 pos 位
    C[d] ← C[d] + 1

  # 前綴和（≤ i 的個數）
  for i ← 1 to r-1:
    C[i] ← C[i] + C[i-1]

  # 回填（由右往左，確保穩定）
  for j ← n downto 1:
    d ← DIGIT(A[j], pos, r)
    B[C[d]] ← A[j]
    C[d] ← C[d] - 1

  copy B[1..n] → A[1..n]

DIGIT(x, pos, r):
  # 以基底 r 取第 pos 位（pos=0 為最低位）
  return ⌊ x / r^pos ⌋ mod r

Radix Sort 分析

• 符號：\(n\) 筆資料；每鍵 \(d\) 位、基底 \(r\)（每位 \(0..r-1\)）。

• 成本拆解：一次回合 \(=\Theta(n+r)\)；總共 \(d\) 回合 ⇒ \(\Theta(d(n+r))\)。

• 線性時間條件：若 \(d=C_1\) 為常數且 \(r=\mathcal{O}(n)\)，所以可視為 \(O(O(n) \times (n+C_1))\)，則為 \(\Theta(n)\)，。

• 備註：桶合併需依 \(0..r-1\) 且 FIFO；否則會破壞穩定性。

Bucket Sort (CLRS) or MSD Radix Sort (DS)

目標：在輸入獨立且均勻於 \([0,1)\) 的假設下，證明 Bucket sort 的期望時間為 \(\Theta(n)\)。

1) 問題設定與演算法

• 輸入：\(x_1,\dots,x_n\in[0,1)\)，彼此獨立且均勻。

• 建 \(m\) 個桶，桶 \(i\) 的區間為 \([\tfrac{i}{m},\tfrac{i+1}{m})\)（CLRS 取 \(m=n\)）。

• 分配：元素 \(x\) 放入桶 \(b(x)=\big\lfloor m,x\big\rfloor\)。

• 各桶內排序（常用 insertion sort）。

• 按桶號 0..\(m-1\) 串接輸出。

BUCKET-SORT(A[1..n], m):
  make buckets B[0..m-1] as lists
  for x in A:
    i ← floor(m * x)
    push x into B[i]
  for i = 0..m-1:
    insertion-sort(B[i])
  return concatenation of B[0],…,B[m-1]

2) 成本分解

令第 \(i\) 桶大小為 \(n_i\)。建桶、分配與串接是線性；瓶頸在桶內排序：

為何是 \(O(n_i^2)\)：插入排序在長度為 \(n_i\) 的序列上成本 \(\Theta(n_i^2)\)。

3) 機率模型與分佈

固定桶 \(i\)，對每個元素定義指示變數，也就是該元素他會不會放在該桶 i 就是該桶 j 就是該元素的 index 然後有放在裡面就是 1，反之：

均勻於 \([0,1)\) ⇒ \(\Pr\big(I^{(i)}_j=1\big)=\tfrac{1}{m}\)，且各 \(I^{(i)}_j\) 彼此獨立。
桶大小是這些指示變數的和：

因此有矩：

4) 期望時間的計算

對 (1) 取期望，並用線性期望：

將 (3) 代入並把常數吸收進 \(O(\cdot)\)：

CLRS 標準選擇 \(m=n\)：

這證明了在均勻獨立且 \(m=n\) 的設計下，Bucket sort 的期望時間為線性。

註：若取一般 \(m\)，(4) 給出 \(\Theta(n)+O(n+n^2/m)\)；只要 \(m=\Omega(n)\)，期望時間仍為 \(\Theta(n)\) 級別。

5) 直觀範例（\(m=4\) 桶）

區間：\([0,0.25)\)、\([0.25,0.5)\)、\([0.5,0.75)\)、\([0.75,1)\)。
資料：\(x={0.12,0.28,0.51,0.77,0.83}\)。

分桶（\(b(x)=\lfloor 4x\rfloor\)）：

• 桶0：\({0.12}\Rightarrow n_0=1\)

• 桶1：\({0.28}\Rightarrow n_1=1\)

• 桶2：\({0.51}\Rightarrow n_2=1\)

• 桶3：\({0.77,0.83}\Rightarrow n_3=2\)

隨機模型下（若 \(x_j\) 來自 \([0,1)\) 均勻）：

• 對固定桶 \(i\)，\(I^{(i)}_j\sim\mathrm{Bernoulli}(1/4)\)。

• \(n_i\sim\mathrm{Bin}(n,1/4)\)，故 \(\mathbb E[n_i]=n/4\)、\(\mathrm{Var}(n_i)=n\cdot\tfrac14\cdot\tfrac34\)。

• CLRS 常取 \(m=n\)，此時 \(\mathbb E[n_i]=1\)，\(\mathrm{Var}(n_i)=1-\tfrac1n\)，且
  \[\mathbb E[n_i^2]=2-\tfrac1n,\]
  進而得 \(\sum_i \mathbb E[n_i^2]=\Theta(n)\)，回到 (5)。

速記版

• 分桶：\(b(x)=\lfloor m x\rfloor\)；CLRS 取 \(m=n\)。

• 成本：\(T=\Theta(n)+\sum O(n_i^2)\)。

• 分佈：\(n_i\sim\mathrm{Bin}(n,1/m)\)，\(\Rightarrow\ \mathbb E[n_i^2]=\tfrac{n}{m}(1-\tfrac1m)+(\tfrac{n}{m})^2\)。

• 結論：\(\mathbb E[T]=\Theta(n)+O(n+n^2/m)\)，特別地 \(m=n\Rightarrow \mathbb E[T]=\Theta(n)\)，如果 n 和 m 相等那麼就是均勻放置那麼代表，會在 \(\Theta(n)\)，如果今天都放在同一個桶子那麼就會變成 \(\Theta(n^2)\)。

Bucket Sort 比較次數小抄

定義

令某桶大小為 \(t\)。以 insertion sort 排此桶的最壞比較次數：

例： \(n=6,\ m=3\)

• 全擠一桶 \((6,0,0)\)：

• 均勻分 \((2,2,2)\)：

一般情況： \((t_1,\dots,t_m)\)

直覺

• 全擠同一桶：\(t_1=n\Rightarrow\sum t_i^2=n^2\Rightarrow O(n^2)\)。

• 均勻分配：\(t_i\approx n/m\Rightarrow\sum t_i^2\approx m\cdot (n/m)^2=n^2/m\)。