Tag Archives: 荷蘭國旗問題

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

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

Posted in 計算算計 | Also tagged | Leave a comment

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

這是一個 O(N-M) 的程式。如果三色數量相同,我們平均需要大約 2(N-M)/3 次交換。如果我們當初選擇從檢查 a[b-1] 開始,平均需要的交換次數則是 N-M 次。

Posted in 計算算計 | Also tagged | Leave a comment

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

陣列裡頭每個元素都是紅、白、藍三色之一。如何把它們由左至右依紅、白、藍的順序排好呢?Dijkstra 希望採用三向分割法後能更容易表達紅(小於 pivot)和藍色(大於 pivot)的區塊絕對比原陣列短的性質。然而,在 Peter 的印象中 Dijkstra 從沒把這層考量寫下來。「我們如果不告訴學生,以後就沒人知道了呢!」他說。

Posted in 計算算計 | Also tagged , | 4 Comments