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

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

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

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

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

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

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で実装してみます。

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のページに戻る。