荷蘭國旗問題 The Dutch National Flag Problem(下)

Quicksort 是實用上表現很好的排序法。眾所皆知,quicksort 的缺點是碰到大致上已排好的、大致上逆向排好的、或著有許多重複元素的陣列時,效率就變差了。若把荷蘭國旗問題用在 quicksort 中,用紅、白、藍三色分別代表小於、等於、大於 pivot 的元素,由於等於 pivot 的元素已被放在一起,應有易於處理重複元素的好處。然而,直到 90 年代中期之前,大家的一般認知是解荷蘭國旗問題需要太多次交換,不值得做。一般做法是把大陣列先用 quicksort 分割,等切得夠小就換成 bucket sort 或 radix sort.

到了 90 年代, Lee McMahon 為第七版 UNIX 寫的 quicksort 函式和其衍生版本已經流傳將近二十年之久。Bentley 和 McIlroy 發現,對所有他們能找到的 quicksort 實作,都可很容易地做個輸入讓它得花輸入長度平方的時間跑完。於是他們決定寫個更有效的 quicksort. 為了處理重複元素,他們又回頭研究了荷蘭國旗問題。

上次我們看了排序 [w,r,b,b,r,b,r,r,b,r,r,w,r,r] 的例子。SrSb 兩種情況的交換分別用 表示。這個例子中,陣列有 14 個元素,而我們用了 13 次交換。

為什麼這麼慢呢?Bentley 和 McIlroy 認為問題出在我們花了太多工夫把兩個白色元素一步步挪到中間(也就是發生的情況)。與其如此,不如先把白色元素放到兩邊去,把陣列排成「白、紅、藍、白」。等排序完成,再把白色換回中間就可以了!他們用的不變量是這樣:

M ≤ w ≤ r ≤ u ≤ b ≤ N ∧ Pw1 ∧ Pr ∧ Pb ∧ Pw2

Pw1 ≡(∀i : M ≤ i < w : white(i))
Pr ≡ (∀i : w ≤ i < r : red(i))
Pb ≡ (∀i : u ≤ i < b : blue(i))
Pw2 ≡ (∀i : b ≤ i < N : white(i))

我用這不變量寫了一個程式:

  w, r, u, b := M, M, N, N
  { Inv: M ≤ w ≤ r ≤ u ≤ b ≤ N ∧ Pw1 ∧ Pr ∧ Pb ∧ Pw2, bound: b - w }
; do r < u →
    if red(r)             → r := r + 1
     | white(r)           → swap(w,r); w, r := w + 1, r + 1
     | blue(r) ∧ red(u-1) → swap(r,u-1); r, u := r + 1, u - 1
     | white(u-1)         → swap(u-1,b-1);  u, b := u - 1, b - 1
     | blue(u-1)          → u := u - 1
    fi
  od
  { M ≤ w ≤ r ≤ u ≤ b ≤ N ∧ Pw1 ∧ Pr ∧ Pb ∧ Pw2 ∧ r = u }

迴圈主體是對稱的五個情況,其中三種需要交換。以下是執行同一個輸入的結果:

確實不僅迴圈執行次數變少(由於 blue(r) ∧ red(u-1) 的情況可把灰色區域縮小兩個元素),交換次數也減少到了六次。當然,我們還需要兩次交換把白色元素放回中間。如果白色元素多,交換次數就多。但 Bentley 和 McIlroy 指出這部份的代價可分配到演算法其他部份去,因為白色元素一旦放到正確位置,便不用再被遞迴排序了。更詳盡的實驗結果可看他們的論文。

這兒的程式和 Bentley-McIlroy 的稍有不同。Bentley-McIlroy 用了兩個迴圈分別推進 r 與 u 的值。我個人比較喜歡這裡的做法,一來迴圈主體和不變量一樣對稱,二來這個程式非必須的限制較少:例如當 red(r) 與 blue(u-1) 都成立,在這裡可看出執行哪個指令對程式的正確性沒有影響。


只是,這麼一來,這迴圈解的好像不是荷蘭國旗問題了。有什麼國旗是「白、紅、藍、白」四色的呢?我找不出分出四條色塊的國旗。如果把顏色交換一下,倒是找到了右邊這幅 Rypin 的旗幟。Rypin 是波蘭的一個小鎮,根據 06 年的統計,人口約一萬六千人。

References

Jon L. Bentley, M. Douglas McIlroy. Engineering a sort function. Software—Practice & Experience 23(11), pp. 1249 - 1265. Nov. 1993.

Justin Peel. Has anyone seen this improvement to quicksort before? Stack Overflow , Jan 20, 2010.

This entry was posted in 計算算計 and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*