Search on the blog

2011年6月25日土曜日

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。じゃなくてピボット選択。

0 件のコメント:

コメントを投稿