計算機演算法 Chapter 8 線性時間排序

第一節 比較排序的下界

比較排序概論

我們已知目前排序演算法的的下界不會低於 $O(n \lg n)$。但是如何證明這件事，就需要用下列 Figure 8.1 的 Decision Tree 來說明：

（圖片來源：Introduction to Algorithms, 2nd ed., Figure 8.1）

而我們可以依圖片統計出看出三個對應關係

1. 內部節點 (有子節點的節點)：決定是哪兩個索引的值要比較 (例如 a 陣列的 decision tree，根結點是 1:2 代表 a[1] 跟 a[2] 比較)
2. 葉節點 (無子節點的節點)：決定最終的排序
3. 分支：決定比較的結果是 $\le$ 或 $>$
   <補充> 這邊用 $\le$ 而不是 $<$ 是為了 stable，即不改變原本值大小相同的元素之間的排列順序

時間複雜度的 Worst Case

為了分析 worst case，我們要統計出最小以及最大的可能性：

1. 葉節點 $l \ge n!$：$n$ 個不同的元素的排列方式有 $n!$ 種，因此葉節點 $\ge$ $n!$
2. 葉節點 $l \le 2^h$：二元樹第 0 層有 $2^0=1$ 個節點 (根節點)、第 1 層有 $2^1=2$ 個節點、第 2 層有 $2^2=4$ 個節點…以此類推，一個二元樹的高度為 h (0 ~ h 層)，因此葉節點 $\le 2^h$

由此可得出 $n! \le l \le 2^h$
$\Rightarrow 2^h \ge n! \Rightarrow h \ge \lg(n!) = \Omega(n \lg n)$
我們得出了 $h \ge \lg(n!) = \Omega(n \lg n)$，而 h 代表的是分支數，分支數又決定了比較的次數，因此可以知道比較排序最低也需要 $\Omega(n \lg n)$ 的時間

第二節 Counting Sort

Pseudocode

1
2
3
4
5
6
7
8
9
10

COUNTING-SORT(A, B, k)
    for i ← 0 to k
        do C[i] ← 0
    for j ← 1 to length[A]
        do C[A[j]] ← C[A[j]] + 1     # C[i] = 等於 i 的元素個數
    for i ← 1 to k
        do C[i] ← C[i] + C[i-1]       # C[i] = 小於等於 i 的元素個數
    for j ← length[A] downto 1
        do B[C[A[j]]] ← A[j]
          C[A[j]] ← C[A[j]] - 1

說明

（圖片來源：Introduction to Algorithms, 2nd ed., Figure 8.2）

依據上面的圖，一步步說明：

1. A 陣列存原本未排序的陣列
2. B 陣列存排序後的陣列
3. C 陣列存累加後的前綴和

輸入 $A = \langle 2, 5, 3, 0, 2, 3, 0, 3 \rangle$，$k = 5$：

放置過程（從 $A[8]=3$ 開始往前）：

最終輸出 $B = \langle 0, 0, 2, 2, 3, 3, 3, 5 \rangle$

第三節 Radix Sort

Pseudocode

1
2
3

RADIX-SORT(A, d)
    for i ← 1 to d
        用 stable 的排序法根據第 i 位大小排序

說明

（圖片來源：Introduction to Algorithms, 2nd ed., Figure 8.3）

輸入 7 個三位數：329, 457, 657, 839, 436, 720, 355

注意排十位後那欄裡的 355 與 457：兩者十位都是 5，但 355 排在 457 前面，這個順序是它們在 排個位數字 階段（5 < 7）就確定的，因為是 stable 的排序方法才可以保留這個順序，因此這說明了為何需要使用 stable 的排序方法做

當 $d$ 為常數且 $k = O(n)$ 時，Radix Sort 為 $\Theta(n)$

第四節 Bucket Sort

Pseudocode

1
2
3
4
5
6
7

BUCKET-SORT(A)
    n ← length[A]
    for i ← 1 to n
        把 A[i] 的值丟進 B[⌊n·A[i]⌋]
    for i ← 0 to n-1
        用 insertion sort 排序 B[i]
    將 B[0], B[1], …, B[n-1] 依據連接起來

說明

因為輸入假設是均勻分布的，平均而言每個桶只會分到 $O(1)$ 個元素，桶內排序成本因此被壓到常數，平均時間複雜度為 $O(n)$，若極端分布的話會降為 $O(n^2)$

輸入 $A = \langle .78, .17, .39, .26, .72, .94, .21, .12, .23, .68 \rangle$，$n=10$，桶 $i$ 負責 $[i/10, (i+1)/10)$：

連接後即為已排序結果（桶 0、4、5、8 為空）
$B = \langle .12, .17, .21, .23, .26, .39, .68, .72, .78, .94 \rangle$

總結

參考文獻

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Ed., The MIT Press, 2001.