［Haskell］ソートアルゴリズムいろいろ

バブルソート

-- 最小値を先頭に
bubble [x] = [x] -- 要素1個ならそのまま
bubble (x:xs)
    | x < y     = x:y:ys -- 1個目が2個目以降の最小値より小さければ入れ替えなし
    | otherwise = y:x:ys -- そうでなければ1個目と2個目以降の最小値を入れ替える
    where
        (y:ys) = bubble xs  -- 2個目以降の最小値を先頭に

-- バブルソート
bsort [x] = [x]          -- 要素1個ならそのまま
bsort xs  = y : bsort ys -- 最小値を先頭に、残りをさらにバブルソート
    where
        (y:ys) = bubble xs -- 最小値を先頭に

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

インサートソート

-- 挿入(要素x, リスト)
insert x [] = [x] -- リストが空なら、x だけのリストに
insert x (y:ys)
    | x < y     = x:y:ys          -- リストの1個目 y が x より大きければ、x をリストの先頭に
    | otherwise = y : insert x ys -- そうでなければ y が先頭になり、2個目以降に x を挿入

-- インサートソート
isort [x]    = [x]                 -- 要素1個ならそのまま
isort (x:xs) = insert x (isort xs) -- 2個目以降をソートした結果に、1個目を挿入

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

マージソート

-- マージ
merge xs [] = xs -- 後半が空なら前半だけ
merge [] ys = ys -- 前半が空なら後半だけ
merge (x:xs) (y:ys) -- 前半の先頭 x と後半の先頭 y を比較して
    | x < y     = x : merge xs (y:ys) -- x が小さいなら先頭に出して残りをマージ
    | otherwise = y : merge (x:xs) ys -- そうでないなら y を先頭に出して残りをマージ

-- マージソート
msort []  = []  -- 空ならそのまま
msort [x] = [x] -- 1個だけならそのまま
                -- 2個以上なら半分に分けて各々マージソートしてからマージする
msort xs  = merge (msort (take h xs)) (msort (drop h xs))
    where
        h = (length xs) `div` 2

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

クイックソート

-- クイックソート
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, 6, 9, 8, 0, 3, 5, 1, 7, 2]