最近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に集めます。集めたleftとrightにそれぞれ再帰的にソートを作用させます。
マージソート
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]
ソートされた二つのリストから小さい順に値をとりだし、一つのリストにまとめ上げます。
結果
むちゃくちゃスッキリしてて書いてて気持ちいい...