常見的排序演算法

Asymptotic Notations 與演算法的關係

一個演算法的 time complexity: 執行時間 = f(輸入資料量) ... 這個函數的成長速率越快, 表示對應的演算法執行速率越慢。

為什麼分析演算法的 time complexity 時, 通常寫 O 而不寫 Theta ? 因為估計過程中, 我們秉持著悲觀, 保守, 寧可高估不要低估的原則, 所以估計出來的函數, 是真正所需執行時間的上限。 (實際上可能不需要那麼久)

Selection Sort

最簡單的排序演算法之一: selection sort (選擇排序): 將 n 張考卷中最低分的那一個調到最前面, 再將剩下 (n-1) 張考卷中最低分的那一個調到第二個位置, 再將剩下 (n-2) 張考卷中最低分的那一個 ...

Selection sort 外層迴圈的 loop invariant: 第 k 步做完時, 所有考卷當中最低分的 k 張已就定位。

Selection sort 的 time complexity: n + (n-1) + (n-2) ... + 2 + 1 屬於 O(n^2)", 意思是如果輸入 n 筆資料, 則最多 (最悲觀的情況下) 花 c n^2 的時間必能用 selection sort 演算法完成排序。 (那個 c 是什麼意思? 就是我們不在意的常數倍。)

Insertion Sort

最簡單的排序演算法之二: insertion sort (插入排序): 最前面 2 張考卷的順序是否需要調整? 最前面 3 張考卷的順序是否需要調整? 最前面 4 張考卷的順序是否需要調整? ...

Insertion sort 外層迴圈的 loop invariant: 第 k 步做完時, 最前面 k 張考卷彼此之間的相關順序正確。 (但將來有可能被其他尚未處理的考卷擠到後面去)

一個排序演算法在完成後, 若能夠保留所有 "值相同" 的資料之間原來的相對順序, 則稱它為 stable。 例如標準版的 selection sort 是 non-stable; 而 insertion sort 容易寫成 stable。 (Q: 寫程式時, 那裡要注意?)

Insertion sort 的 time complexity: 1+2+3...+n 屬於 O(n^2); 但運氣好的話, 最快只需要 O(n)。 Q: 怎麼樣的情況會造成執行時間只需要 O(n)?

請見 selection sort 與 insertion sort 的範例

Mergesort

先前 看過的 mergesort 是一種 divide-and-conquer 類型的演算法 -- 把一個大問題切成幾個小一號的問題, 個個擊破。 如果這些小一號的問題, 與原問題長得很像, 就可以寫 遞迴 recursive 程式來解。

摘要: 「把資料等分成兩堆, 各自用 mergesort 排序好後再合併。」 其中最主要的工作都在 "合併" 動作當中完成。

Mergesort 有兩種: top-down 及 bottom-up。 請見 範例。

分析 mergesort 的 time complexity: 只考慮 n = 2^k 這種狀況, 因為這種狀況比較容易算, 更重要的是因為只考慮這種狀況就夠了。 (記得嗎? "不在意零頭, 不在意常數倍; 在意的是趨勢, 是成長的速度.") 耗時 T(n) = 2*T(n/2) + n

一個排序演算法, 若只需要用到 O(1) 的額外空間, 則稱它具有 in-place 特性。 例如 insertion sort, selection sort 都是 in-place。 但 merge sort 就不是 in-place, 它在 merge 時耗費 O(n) 的空間。

Mergesort 可以是 stable (Q: 寫程式時, 那裡要注意?)。

Quicksort

Quicksort 也是一種 divide-and-conquer 類型的演算法, 也可以用遞迴來實作。

摘要: 「挑一個元素當做 pivot, 把陣列內比它小元素的都放在同一側; 把比它大的都放在另一側。 然後對兩側使用 quicksort。」 請見 範例程式。 可以修改 @a = qw(...) 那一句, 換不同的資料來測試看看。

如何分側? 「從左右向中間掃描, 每找到一對放錯側的元素, 就把它們對調過來。 對調後繼續向中間掃描, 直到兩個指標交錯為止.」 這個分側動作叫做 partition 注意: 完成 partition 動作後, 這個 pivot 元素自然也就落到它最終的正確位置。

簡單版的 quicksort 以陣列的最左邊元素作為 pivot。 執行方式: ./qsort -g -p left

Time complexity:

  1. best case: O(n lg n), 因為 T(n) = 2*T(n/2) + n
  2. worst case: O(n^2), 因為 T(n) = T(n-1) + n
  3. average case: O(n lg n) (即使是 T(n) = T(9n/10) + T(n/10) + n 這麼不理想的情況, 還是 O(n lg n), 所以 ...)

Quicksort 不適合用於「幾乎已排好」或「幾乎正好排顛倒」的資料。

改進一: randomized quicksort: 用亂數決定要選取那一個元素當做 pivot, 而不是固定找第一個元素。 不論是 best/worst/average case 的 time complexity 都沒有改變; 但是如此可以避免上述狀況經常發生。 請執行 ./qsort -g -p rand 看看

改進二: median-of-3 quicksort: 挑陣列的第一個, 中間的, 及最後一個元素, 用這三個之中的中位數 (median) 來當做 pivot。 除非這三個數字當中正好有兩個非常小, 或有兩個非常大 (機率很小), 否則所選出來的 pivot 應該可以讓 partition 把陣列分得比較平均些。 請執行 ./qsort -g -p mo3 看看

可以把以上兩種改進合併, 先用亂數任選三個, 再用其中的 median 當做 pivot。

改進三: 運用 insertion sort 的特性 (若資料原本就幾近排序完成, 則 insertion sort 只需花 O(n) 的時間), 修改 quicksort: 遞迴到陣列內少於 k 個元素時, 就不要遞迴下去了。 每一小段 k 個元素都放著不排序, 等最上層 quicksort 完成後, 再一次呼叫 insertion sort 來收拾殘局。

Q: Quicksort 是否為 stable? Q: Quicksort 是否為 in-place? 表面上好像是; 其實因為它遞迴, 所以用了 stack 空間。 Q: Quicksort 最壞的情況下會用到 O(n) 的 stack 空間。 什麼樣的情況? Q: 如何改寫 quicksort, 讓它使用的 stack 空間不超過 O(lg n)? Q: Mergesort 也是遞迴, 為什麼我們先前沒有討論使用 stack 空間的問題?

題外話: 寫程式時應善用系統既有的資源。 許多程式語言的函式庫當中都已有現成的 quicksort, 應多加利用。 例如 C 當中的 qsort 即是。 但要學會使用 指到函數的指標變數。

如果你一定要自己寫 quicksort 程式, 這裡有一些細節及心得與你分享:

  1. 兩頭需要有 sentinel 來阻止兩指標跑過頭。 如果你以最左或最右元素為 pivot, 就可以省掉一個 sentinel。 在排中間段落的時候, 兩邊的資料自動成為 sentinel。 如果你用 median-of-3, 那麼兩頭的 sentinel 都可以省略掉。
  2. 左右指標在跑的時候, 為什麼遇到與 pivot 等值的元素也要停下來? 這樣 pivot 本身就可以作為 sentinel。
  3. 每次左右兩指標交錯, partition 動作結束後, 你的左 pivot 應與右指標的元素對調 (因為當時它已指向較小元素); 反之, 如果當初你以右元素為 pivot, 那麼此時應將 pivot 與左指標的元素對調。
  4. 若要選其他元素作為 pivot, 請先將它與左 (右) 元素對調, 程式比較好寫。

Mergesort 與 Quicksort 其實很像

Mergesort 與 Quicksort 的比較: 都是 Divide-and-Conquer 的演算法, 只是 quicksort 先苦後樂 (進入遞迴之前的 partition 動作比較麻煩; 遞迴結束之後什麼都不必再做) 而 mergesort 先樂後苦 (進入遞迴之前什麼都不必做; 遞迴結束之後的 merge 動作比較麻煩)。

        void quicksort(...)             void mergesort(...)
        {                               {
            partition(...);

            quicksort(...);                 mergesort(...);
            quicksort(...);                 mergesort(...);

                                            merge(...);
        }                               }