MIT 6.006 Introduction to Algorithms 7.2
7. Counting Sort, Radix Sort, Lower Bounds for Sorting
提要
由於 Comparison Model 的限制，我們無法將 Search, Sort 的速度提升，我們需要upgrade model來提升效率。
如何upgrade ? RAM（Random Access Machine）是一個好的辦法！
With the power of RAM, you can access every things in array with a linear time.
結論
本篇介紹的兩種 Algo.：
- Counting Sort (Integer Sort) … Time Cost ≥ N + k
- Radix Sort … Time Cost ≥ N
兩者利用改變Comparison Model的限制（把數字轉成文字處理，讓原本≤, ≥, =的運算元變得更多元。對文字做拼裝, 拆解等等的constant time運算），已達到Sort Time Cost ≥ N 的速度
當然，對於這樣快速Sorting的Algo.，必須要有以下的限制：
- Sorting的物件，一定要是Integer
- 每個物件可以被轉譯成文字處理（int 2016 > String “2”, “0”, “1”, “6”）
- 可以做除了Comparison以外的operation
- 物件中的最大整數值 k ，不可以太大（k < N ^ C，k不可大於以N為底的constant指數）
讓我們利用實體例子，來解釋兩種algo.
Counting Sort （Integer Sort）
假設你有一個Integer Array Input：
Input = [ 3, 4, 1, 2, 3, 5]Maximum = 5
請建立負責儲存算數結果的Count Array，而且array的空間剛好就是整數的最大值 5 + 1
Counter = [ 0, 0, 0, 0, 0, 0]接著 For Loop 一次 Input，並且計算每個數字出現的個數，加總至Counter，最後的結果應該會像這樣：
Counter = [ 0, 1, 1, 2, 1, 1]數字 3 在整個 Input 中出現 2 次，所以他在counter上的數字是 2 （Counter[3] = 2）
從這個Counter，你可以知道：
- 數字 “0” 出現 0 次
- 數字 “1” 出現 1 次
- 數字 “2” 出現 1 次
- 數字 “3” 出現 2 次
- 數字 “4” 出現 1 次
- 數字 “5” 出現 1 次
最後針對這些統計，跑一次 For Loop ，把答案從 0 到 5 輸出，出現幾次就append幾個數字，最後就會是sorting的結果：
Answer = [ 1, 2, 3, 3, 4, 5 ]Counting Sort 的 Time Cost 是多少呢？
- 建立長度為 k 的 Counter Array = O(k)
- for loop 長度為 N 的 Input Array = O(N)
- for loop 長度 k 的 Counter Array 並 append N 個 物件 = O(N + k)
Counting Sort 所花時間總共為 O(N + k)
k 為最大整數值，N 為 Sorting 的物件數量
你可以發現，最大整數值 k 不可以太大，不然 Counting Sort 就會變慢，這也是接下來，Radix Sort要解決的
Radix Sort
讓我們直接從實例了解：
Input = [ 72, 21, 6, 25, 17 ]
k = 72這時，請針對個位數做一次Counting Sort
CountingSortInput1 = [ _2, _1, 6, _5, _7 ]Result1 = [ 21, 72, 25, 6, 17]
接下來，把 Result 1 再針對十位數做一次Counting Sort
CountingSortInput2 = [ 2_, 7_, 2_, 0, 1_]Result2 = [ 6, 17, 21, 25, 72]
這時你發現，Result 2 已經是 Sorting 好的了，神奇！
Radix Sort 是 Counting Sort 的一種延伸，他為了讓 k 不要太大，他把每次counting的範圍都控制在基數 b ，並分多次完成（Divide & Conquer）
我們利用每次只處理一位數（b = 10），來讓最大值 k 從原本的 72, 降到 10 以下（原本需要建立空間大小為72個的 Counter Array ，減少到空間為 10 個），每次 Counting Sorting 的時間（N+b），並分 d 次執行（本範例執行 2 次）
Radix Sort Time Cost = ( N + b ) * d
經由幾個假設：
- b = N
- k ≤ N^C
我們可以得到一個快速的結果：
Radix Sort Time Cost = O( N )
下一堂影片，將介紹利用 hashing技術，超越這個 O( N ) 的速度！