Haskellでクイックソート

すごいHaskellたのしく学ぼう!

「4.3 クイック、ソート！」版

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x : xs) =
    let left = [n | n <- xs, n <= x]
        right = [n | n <- xs, n > x]
    in qsort left ++ [x] ++ qsort right

「5.3.2 filter関数」版

qsort' :: (Ord a) => [a] -> [a]
qsort' [] = []
qsort' (x : xs) =
    let left = filter (<= x) xs
        right = filter (> x) xs
    in qsort left ++ [x] ++ qsort right