Haskellで挿入ソート
を書いてみました。が、普通のよくあるC言語の実装例とは違って外部にリストを持たせてます。このアルゴリズムだと入力のリストがすでに昇順に並んでいると高速に動作します。
module Main (main) where
insertsort :: [Int] -> [Int]
insertsort = foldr insert []
where
insert x xs =
let (xs1, xs2) = span (x >) xs
in xs1 ++ x : xs2
main :: IO ()
main = print $ insertsort [8, 4, 3, 7, 6, 5, 2, 1] -- => [1,2,3,4,5,6,7,8]
