Haskellで有名アルゴリズム実装（3）

今回は、クイックソート。

Haskellでのクイックソートの実装は、とても美しく、もっとも美しいコードの一つにあげる人も多いです。

view plainprint?

1. qsort :: (Ord a) => [a] -> [a]  
2. qsort []     = []  
3. qsort (x:xs) = (qsort left) ++ [x] ++ (qsort right)  
4.                where left  = filter (<x)  xs  
5.                      right = filter (>=x) xs  

qsort :: (Ord a) => [a] -> [a]
qsort []     = []
qsort (x:xs) = (qsort left) ++ [x] ++ (qsort right)
               where left  = filter (<x)  xs
                     right = filter (>=x) xs

　これで、クイックソートが出来ます。毎回リストの先頭をピボットに選択して、分割統治しています。

これだけだと、ちょっとさびしいのでクイックソートに最悪入力パターンを与えてみます。

view plainprint?

1. main = print $ qsort [10000,9999..1]  

main = print $ qsort [10000,9999..1]

　私の環境では、処理が完了するまで20秒ほどかかりました。クイックソートの理想的な場合の計算時間は長さnのリストをn/2とn/2のリストに分割して、再帰処理をするため、O(n*log n)です。が、もともとほぼ整列しているリストや、逆順にソートされているリストの場合は、nが1とn-1に分かれてしまうため、全体の計算量はO(n*n)になってしまいます。

クイックソートでは、leftとrightが均等に分かれるようなピボット選択が重要です。良く知られたピボット選択方法としては、

• ランダムな要素を選択する
• 中央の要素を選択する
• 先頭、中央、末尾の要素の中央値を選択する

などがあります。3つ目のピボット選択をHaskellで実装してみます。

view plainprint?

1. selectPivot :: (Ord a) => [a] -> a  
2. selectPivot x = let xh = head x  
3.                     xm = x !! (div (length x) 2)  
4.                     xl = last x  
5.                 in median [xh, xm, xl]  
6.   
7. median :: (Ord a) => [a] -> a  
8. median xs = let sortedXs = qsort xs  
9.                 midIndex = div (length xs) 2  
10.             in sortedXs !! midIndex  
11.   
12. balancedQsort :: (Ord a) => [a] -> [a]  
13. balancedQsort [] = []  
14. balancedQsort xs = (balancedQsort left) ++ [x] ++ (balancedQsort right)  
15.                       where x     = selectPivot xs  
16.                             xs'   = delete x xs  
17.                             left  = filter  (<x) xs'  
18.                             right = filter (>=x) xs'  

selectPivot :: (Ord a) => [a] -> a
selectPivot x = let xh = head x
                    xm = x !! (div (length x) 2)
                    xl = last x
                in median [xh, xm, xl]

median :: (Ord a) => [a] -> a
median xs = let sortedXs = qsort xs
                midIndex = div (length xs) 2
            in sortedXs !! midIndex

balancedQsort :: (Ord a) => [a] -> [a]
balancedQsort [] = []
balancedQsort xs = (balancedQsort left) ++ [x] ++ (balancedQsort right)
                      where x     = selectPivot xs
                            xs'   = delete x xs
                            left  = filter  (<x) xs'
                            right = filter (>=x) xs'

上の実装だと、先ほどのデータに対しても1秒以下でソートが出来ました。恐るべしHaskell。じゃなくてピボット選択。

Haskellのページに戻る。