Search on the blog

2011年7月10日日曜日

クイックソート VS マージソート

今日は、軽い実験。Haskellの練習がてら、quick sortとmerge sortを比較する。

まず、quick sort。
-- quick sort
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = let left = filter (<x) xs
right = filter (>=x) xs
in qsort left ++ [x] ++ qsort right
Haskellは美しい。次に、merge sort。
msort :: (Ord a) => [a] -> [a]
msort [x] = [x]
msort [x, y] = [min x y, max x y]
msort xs = let len = length xs `div` 2
pre = msort $ take len xs
suf = msort $ drop len xs
in merge pre suf

merge [] [] = []
merge x [] = x
merge [] y = y
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
もうちょっと綺麗に書けそうだが、こんなもんだろう。
適当に乱数をソートしてみる。
getRandoms :: Int -> [Int]
getRandoms n = take n $ randomRs (1, 100000) $ mkStdGen 0
n=100,000で比較。
quick sort 0.653[s]
merge sort 0.891[s]

quick sortの弱点を突いてみる。ソート済みのリストを入力として与えてみる。[1..100000]で比較。
quick sort 815.877[s]
marge sort 0.465[s]

quick sortはpivot選択すれば改良はできるけど、それでも理論上の最悪計算量はO(n^2)。merge sortは常に平衡二分木を形成するように分割するので、計算量は常にO(n log n)。ランダムなデータに対してはquick sortが速い場合が多いようだが、実用上はmerge sortを使用した方が安心な気がする。

0 件のコメント:

コメントを投稿