ソートをいろいろ

Haskell 30分プログラム

30分プログラム、その157。インサーションソートのアルゴリズムを確認したくなったので、さくっと作ってみる。

ただ、インサーションソートだけだと寂しかったので、マージソートをクイックソートをば。

使い方

*Main> isort [42,1,5,9]
[1,5,9,42]

*Main> msort [42,1,5,9]
[1,5,9,42]

*Main> qsort [42,1,5,9]
[1,5,9,42]

ソースコード

-- 目的のinsertソート
insert :: (Ord a) => a -> [a] -> [a]
insert v [] = [v]
insert y l@(x:xs) = if x < y then
                        x:insert y xs
                    else
                        y:l

isort :: (Ord a) => [a] -> [a]
isort = foldl (flip insert) []

-- オマケのマージソート
merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge l@(x:xs) r@(y:ys) = if x < y then
                              x:merge xs r
                          else
                              y:merge l ys
msort :: (Ord a)=>[a]->[a]
msort [] = []
msort [x] = [x]
msort xs = let (left,right) = splitAt (length xs `div` 2) xs 
           in  merge (msort left) (msort right)

-- 有名なクイックソート
qsort :: (Ord a)=>[a]->[a]
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs , y < x ] ++
               [x] ++
               qsort [y | y <- xs , y >= x]

参考