Sorting in Linear Time Michael Tsai 2013/5/21

Sorting Algorithm in Linear Time? 上回講過, Comparison-based (比較元素然後交換其順序) sorting的complexity lower bound為Ω 𝑛 log 𝑛 如何突破這個障礙? 不要使用comparison-based的方法 因此可達到𝑂 𝑛 需要利用額外的假設 通常是”以空間換取時間”

例子: 電話排序問題 電話排序假設全部電話號碼有s個種可能 (所有排列組合) 我們有n組電話要排 則使用超大表格排序法需要O(s)的時間 (空間換取時間) Input: {20000002, 89999999, 20000000, …} Index 20000000 空 20000002 … 89999999 Array 有 空 … 共s個

例子: 電話排序問題 如果使用comparison-based sorting平均需要𝑂 𝑛 log 𝑛 假設超大表格排序法所需時間為 𝑐 1 𝑠 假設comparison-based排序法所需時間為 c 2 𝑛 log 𝑛 假設10 𝑐 1 = 𝑐 2 break even point為 s= 10 n log n 假設以台北市電話號碼為例, 𝑠= 10 8 10 8 =10 𝑛 log 𝑛 , n< 10 8 break even point大約為 n=k ×10 6 當n大於此數則non-comparison sorting比較快

Counting Sort 假設: 知道可能出現的所有input種類個數K (而且𝐾=𝑂 𝑛 ) Input array “Cumulative Mass Function” 算小於或等於index的數字出現了幾次 Counting: 算每個數字出現了幾次

Counting Sort 比3小或相等的有7個

Counting Sort 比0小或相等的有2個

注意Counting Sort為stable sort 注意Counting Sort為stable sort. 因為是從最後面依序放入output array, 因此同樣大小的元素會依原本input array中順序放入. Counting Sort

A: input array n: input總個數 B: output array K: 可能出現的input element總數 Counting Sort void CountingSort (int A[], int n, int B[], int K) { int C[K], i, j,; for (i=0;i<K;i++) C[i]=0 for (j=0;j<n;j++) C[A[j]]=C[A[j]]+1; for (i=1;i<K;i++) C[i]=C[i]+C[i-1]; for (j=n-1;j>=0;j--) { B[C[A[j]]]=A[j]; C[A[j]]--; } 𝑂(𝐾) Counting: 數每種element共幾個 𝑂(𝑛) 𝑂(𝐾) “CMF”: 數比每種element小或相等的共幾個 𝑂(𝑛) 從input array最後一個開始依序放入output array 𝑂 𝑛+𝐾 =𝑂(𝑛)

Sorting on several keys 假設K有很多個sub-key 𝐾=( 𝐾 1 , 𝐾 2 ,…, 𝐾 𝑟 ) 則 𝐾 𝑥 ≤ 𝐾 𝑦 iff 𝐾 𝑥,𝑖 = 𝐾 𝑦,𝑖 , 1≤𝑖≤𝑗 𝑎𝑛𝑑 𝐾 𝑥,𝑗+1 < 𝐾 𝑦,𝑗+1 for some 𝑗<𝑟, or 𝐾 𝑥,𝑖 = 𝐾 𝑦,𝑖 , 1≤𝑖≤𝑟 則我們可以有以下的sorting 方法. Most Significant Digit first (MSD) sorting 先依照most significant key sort, 然後依序往least significant key sort過去 Least Significant Digit first (LSD) sorting 先依照least significant key sort, 然後依序往most significant key sort過去 Most significant key Least significant key

Radix Sort 假設:有”多個key” 以個位數排序 以十位數排序 以百位數排序 329 457 657 839 436 720 355 720 355 436 457 657 329 839 720 329 436 839 355 457 657 329 355 436 457 657 720 839 注意: 十進位一樣的部分 會照前一回合的順序 (也就是個位數的順序!) 因此用來排序的演算法 必須是stable! 先依照least significant digit sort, 然後依序往most significant key sort過去: Least Significant Digit first (LSD) sorting

Radix Sort 如果先依照most ignificant key sort, 然後依序往least significant key sort過去: Most Significant Digit first (MSD) sorting? 正確的做法必須切分成小的subset再去排序! (因此MSD比較麻煩) 以百位數排序 以十位數排序 329 457 657 839 436 720 355 329 355 457 436 657 720 839 329 720 436 839 355 457 657 329 355 436 457 657 720 839 如果直接使用接下來的十位數排序 會亂掉!

Radix Sort 以個位數排序 以十位數排序 以百位數排序 329 457 657 839 436 720 355 720 355 𝑂(𝑛) 𝑂(𝑛) 𝑂(𝑛) 假設使用Counting Sort在每一回合做排序 d個, d=位數 𝑂(𝑑𝑛)

Bucket Sort 假設: input是從uniform distribution取出來的 同樣bucket的再使用簡單的insertion sort做排序 最後再把各bucket內的元素依序列出即可

Bucket Sort 假設: input是從uniform distribution取出來的 因此分到各個bucket的數量會差不多. 大略計算一下所需的時間: 𝑇 𝑛 =Θ 𝑛 + 𝑖=0 𝑛−1 𝑂( 𝑛 𝑖 2 ) 𝐸 𝑇 𝑛 =E Θ 𝑛 + 𝑖=0 𝑛−1 𝑂 𝑛 𝑖 2 =Θ 𝑛 + 𝑖=0 𝑛−1 𝑂 𝐸[𝑛 𝑖 2 ] =Θ 𝑛 +𝑛 ⋅𝑂 2− 1 𝑛 =Θ(𝑛) 走過每個bucket的時間 每個bucket內insertion sort所需時間 總時間 𝐸 𝑛 𝑖 2 =2− 1 𝑛 (證明過程請見Cormen p202-203)

Today’s Reading Assignment Cormen 8.2, 8.3, 8.4