Edited at

Haskellでクイックソートとマージソート

最近Haskellを勉強し始めたのでアウトプットのためクイックソートとマージソートを書いてみた。


クイックソート

quickSort [] = []

quickSort [x] = [x]
quickSort (x:xs) = quickSort left ++ [x] ++ quickSort right
where left = filter (< x) xs
right = filter (>= x) xs

main = do
print $ quickSort [1, 8, 7, 6, 2, 5, 9, 4, 0, 3]

リストの先頭要素をピボットにしてピボットより小さい要素をleftにピボット以上の要素をrightに集めます。集めたleftrightにそれぞれ再帰的にソートを作用させます。


マージソート

merge xs [] = xs

merge [] ys = ys
merge (x:xs) (y:ys)
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort (left)) (mergeSort (right))
where left = take half xs
right = drop half xs
half = length xs `div` 2

main = do
print $ msort [1, 8, 7, 6, 2, 5, 9, 4, 0, 3]

ソートされた二つのリストから小さい順に値をとりだし、一つのリストにまとめ上げます。


結果

むちゃくちゃスッキリしてて書いてて気持ちいい...


参考文献

Haskell 超入門