總結排序

題外話: 8 顆硬幣問題

有 8 顆外觀一模一樣的硬幣, 已知其中恰有一顆偽幣, 它的重量比其他 7 顆都輕。 如果要用天平找出偽幣, 至少要秤多少次?

                        演算法一: 逐一比較
                           1:2
                            |
                     ---------------
                     |      |      |
                     1     3:4     2
                            |
                     ---------------
                     |      |      |
                     3     5:6     4
                            |
                     ---------------
                     |      |      |
                     5     7:8     6
                            |
                     ---------------
                     |             |
                     7             8

觀察:

  1. 每片葉子代表一種可能出現的答案。
  2. 從 root 到達一片葉子的這條 external path, 就是某次的執行過程。
  3. 樹的高度就是使用天平的次數。 (worst case)
  4. 可能出現的不同答案, 總共只有 8 個 ("1 號比較輕", "2 號比較輕", ..., "8 號比較輕".)

結論: 希望樹要長得矮矮胖胖, 越平衡越好

                        演算法二: 分群比較
                        1234:5678
                            |
                -------------------------
                |                       |
              12:34                   56:78
                |                       |
            -----------           -----------
            |         |           |         |
           1:2       3:4         5:6       7:8
            |         |           |         |
          -----     -----       -----     -----
          |   |     |   |       |   |     |   |
          1   2     3   4       5   6     7   8

Q: 有沒有更快 (比較次數更少) 的演算法? 每次使用天平所得到的答案, 只有兩種可能性嗎? 若不然, 則「使用次數」與「可產生不同結果數」之間有何關係? 請發明 "演算法三: 3*3=9>8" Q: 如果還是只限定使用天平, 需要再花力氣去想 "比演算法三更快" 的演算法嗎?

所有排序演算法的耗時下限

Q: 可以找到比 mergesort 及 heapsort 更快 (更有效率, 具有更低的 time complexity) 的演算法嗎?

嚴格定義: 排序問題的 worst case lower bound: 把所有已發明的及未發明的排序演算法一個一個列舉出來, 針對每個演算法的特性, 設計出一系列 (1 個元素, 2 個元素, ... n 個元素, ...) 最折磨這個演算法的資料, 並計算它耗費的時間。 從而由每個演算法衍生出一個 n 的函數 (而不只是一個數字)。 把所有函數搜集起來, 這個集合的下限就是排序問題的 worst case lower bound。

要證明排序問題的 worst case lower bound 屬於 Omega(n) 很容易: 任何演算法總要把所有的元素都看過一遍才能排得出順序吧? 那至少就已經花了 c n 的時間了。

排序問題的下限: 「n 個元素的排序問題」 可能有 n! 種不同的答案。 不論是那種演算法, 只要它以「比較兩數」的方式來區分不同的答案, 每比較一次至多也不過就是把這 n! 種答案分成兩群。 所以至少要 lg(n!) 個比較才能完全分辨出所有不同的答案。 也就是說, 排序問題的 worst case time complexity 屬於 Omega(n lg n)。

(以上證明的詳細說明:) 把你最喜歡的排序演算法拿來, 考慮它如何處理一個「n 個元素」的問題。 先不看輸入的資料, 只看演算法本身: 每執行到一個 if 敘述, 就畫一對分枝, 代表兩種可能不同的結果。 這形成了一棵 decision tree。 再考慮輸入一組 n 個元素的資料: 如此執行一次, 在樹上就可以看到一個 external path 從 root 往 leaf 一路亮起來。 既然要能把所有 n! 種不同的輸入分別引導到 n! 個不同的分支去, 這棵樹的 leaves 至少要有 n! 個; 而它的高度至少要有 lg(n!)。

我們若能找出一個演算法, 它的時間複雜度正好與這個問題的時間複雜度下限相同, 就稱這個演算法為這個問題的一個 asymptotically optimal algorithm。 (嚴格來說, 應該說: 「...它的 time complexity 所屬集合 與這個問題的 time complexity 所屬集合有交集...」) 例如 mergesort 與 heapsort 都是 asymptotically optimal sorting algorithm。 通常也唯有此時, 才將這個演算法的 time complexity 記成 Theta(...) 而不是 O(...)

一個問題, 如果可以證出來的時間複雜度下限, 與找得到的最佳演算法的時間複雜度之間有差距, 就表示 (1) 證明還不夠好 (問題的時間複雜度下限應該更高; 問題比我們所理解的更難) 或者 (2) 演算法還不夠好 (還有時間複雜度更低的演算法; 問題比我們理解的更簡單) 或者 (3) 以上皆是。

非比較類的排序法

若輸入資料具有某些特性, 我們可以揚棄用 「比較元素」的方式來排序, 而打破 Omega(n lg n) 的下限。 Counting sort 假設輸入資料都是整數, 且數值範圍較諸元素個數而言, 並不太大。 例如輸入 3000 個四位數的偶數 (元素個數 n=3000; 不同數值共有 k= 5000 個)。 請參考 一個簡單範例 並自己執行 範例程式:

  1. 建一個陣列 C[1..k], 記錄每個輸入數值各出現幾次。
  2. 累計 C[1..k] 內的值, 讓 C[i] 變成記錄「小於或等於 i 的元素在輸入資料當中出現過幾次?」
  3. 從輸入陣列的後面開始, 逐一把每個元素 x 丟到它正確的輸出位置。 (也就是輸出陣列的第 C[x] 個位置.) 注意每次解決一個值為 x 的元素, 就應該把 C[x] 的值減一, 這樣萬一有其他值同樣為 x 的元素, 將來就會放到現在這個 x 的前面, 而不會與現在這個 x 重疊輸出。

為什麼在 counting sort 的最後一步, 要從輸入陣列的後面開始處理? 這樣才可以滿足 stable 的特性。

耗時: (k + n) + k + n 屬於 O(n+k) (最前面的 k 是把 C[1..k] 歸零的時間。)

速度這麼快, 代價是大量使用額外空間: O(n+k)

Q: 如果輸入資料是 50 個 -0.99 到 0.99 之間的二位小數, 應如何使用 counting sort?

Radix sort: 也是用在整數資料的排序方法。 先按照最後一位數 (呼叫某個 stable 排序法) 排序, 再按照倒數第二位數排序, ... 最後按照第一位數排序。 請見 範例 並執行 程式

為什麼先按照最後一位數排 ... 最後才按照第一位數排? 如果先按照第一位數排 ... 最後再按照最後一位數排, 則先前排好的順序都亂掉了。 我們反過來排, 最後的動作 (第一位數) 決定真正的順序; 至於第一位數相同而後面不同的數字, 其順序為何正確? 因為我們所選用的「某個排序法」是 stable。

Time complexity: 視底層的「某個 stable 排序法」的 time complexity 而定。 假設有 n 筆輸入資料, 每筆資料為 d 位的 k 進位數 (例如 2f5c 可以算作是一個 4 位的 16 進位數), 又假設「某個 stable 排序法」 是 counting sort, 則耗時 O((n+k)d)。

例: 對 10^6 個 64-bit 整數用 radix sort 排序, 把每個整數視為一個 4 位的 2^16 進位數, 則要對這 10^6 個數字處理 8 回; 若用一般的 optimal comparison sort, 至少要對這 10^6 個數字處理 lg(10^6) = 20 回。

Bucket sort: 輸入資料不限定是整數。 找出 (或由題目給定) 輸入的 n 筆資料的範圍, 將這個範圍等分成 n 份 (想像有 n 個桶子)。 如此一來直接看每筆資料的值就知道要將它放入那個 bucket。 如果資料分佈還算均勻的話, 每個 bucket 內的元素個數不會太多, 可直接用 insertion sort 排序。 最後再把所有 buckets 內排序完畢的資料串起來輸出。

Average case time complexity: O(n) (假設資料均勻分佈)

如果下層的排序法是 stable, 則 bucket sort 也可以是 stable。

排序 (sorting) 所需時間下限: Omega(n lg n)
輸入: n 個數字; 輸出: 同樣這 n 個數字, 由小到大排好。
名稱 時間 額外空間 stable? 摘要
selection O(n^2) O(1) no 從剩下的元素中挑出最小的
insertion O(n^2) O(1) yes 把下一個元素向前推進至正確的位置
merge O(n lg n) O(n) yes 等分成兩堆, 各自排好再合併
quick O(n^2) O(lg n) no 挑一個 pivot 就定位; 且使小元素皆在左, 大元素皆在右
heap O(n lg n) O(1) no 不斷新增, 再不斷刪除; 採用新增刪除都花 O(lg n) 的 heap
counting O(n+k) O(n+k) yes 元素依值對號入座, 一次就定位。
radix O((n+k)*d) O(n+k) yes 重複呼叫某 stable sort, 從最末位開始, 排序數次

如果你真的有資料需要排序

如果你對理論/寫程式有興趣, 那麼確實是非常值得拿排序問題來練習寫程式。 (我自己也很喜歡寫一些沒有用的程式, 像唱歌跳舞一樣 "純屬樂趣") 然而如果要對資料排序, 是你的工作, 而不是你的興趣, 那麼實在應該避免自己 寫 排序函數, 而要學會 用 排序函數: 把函數當做資料來用