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

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

まず、quick sort。

view plainprint?

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

-- 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。

view plainprint?

1. msort :: (Ord a) => [a] -> [a]  
2. msort [x] = [x]  
3. msort [x, y] = [min x y, max x y]  
4. msort xs = let len = length xs `div` 2  
5.                pre = msort $ take len xs  
6.                suf = msort $ drop len xs  
7.            in merge pre suf  
8.   
9. merge [] [] = []  
10. merge x []  = x  
11. merge [] y  = y  
12. merge (x:xs) (y:ys)  
13.      | x <= y    = x : merge xs (y:ys)  
14.      | otherwise = y : merge (x:xs) ys  

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

もうちょっと綺麗に書けそうだが、こんなもんだろう。

適当に乱数をソートしてみる。

view plainprint?

1. getRandoms :: Int -> [Int]  
2. getRandoms n = take n $ randomRs (1, 100000) $ mkStdGen 0  

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を使用した方が安心な気がする。