読者です 読者をやめる 読者になる 読者になる

fnwiyaBlog

EmacsとかLispとか可視化とか

haskellでバブルソート・マージソート・クイックソート

Haskellでソート3種実装してみました。
クイックソートのシンプルさが際立ちます。
これがパターンマッチの力。

バブルソート

bswap [x] = [x]
bswap (x:xs)
    | x > y     = y:x:ys
    | otherwise = x:y:ys
    where
        (y:ys) = bswap xs

bsort [] = []
bsort xs = y : bsort ys
    where
        (y:ys) = bswap xs

main = do
    print $ bsort [4, 3, 1, 5, 2, 7, 3]

マージソート

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

msort []  = []
msort [x] = [x]
msort xs  = merge (msort (take h xs)) (msort (drop h xs))
    where
        h = (length xs) `div` 2

main = do
    print $ msort bsort [4, 3, 1, 5, 2, 7, 3]

クイックソート

qsort []     = []
qsort (n:xs) = qsort lt ++ [n] ++ qsort gteq
    where
        lt   = [x | x <- xs, x <  n]
        gteq = [x | x <- xs, x >= n]

main = do
    print $ qsort [4, 3, 1, 5, 2, 7, 3]