ソート！ソート！ソート！

今回のお題はソートです。今までは移植を順番にしてきましたがなんとなくイレギュラーにやります。ていうか、確かに移植対象もソートだったんですが各ソートごとにサンプルがあったので1回にまとめました。
ソートなんてだいたいどの言語でも標準ライブラリとかあるので余程の理由が無い限りは自作することは無いと思います。haskellにも多分あるんじゃないかな？まあ実装演習が目的なのでとにかく作ります。
一言にソートと言ってもいろいろあるわけで、今回は代表的なソートをいくつか実装しました。実装が目的なので、実際にはそのソートアルゴリズムの利点をちゃんと活かしていないのもありますが、まあそこは目をつぶってください（＾＾；

-- クイックソート
quickSort _ [] = []
quickSort f (n:ns) = ( before f n ns ) ++ (n:(after f n ns))
    where before f n ns = quickSort f $ filter (not.f n) ns
          after  f n ns = quickSort f $ filter (f n) ns

まあ典型的な例ですね。大抵のhaskellの本に載ってますしwikipediaにもありますね。通常、実装が割と大変なクイックソートですが、haskellでは逆に簡単になります。

-- バブルソート
bubbleSort f ns = bubbleNext f $ bubbleDown f ns
    where bubbleNext _ []     = []
          bubbleNext f (n:ns) = (n:) $ bubbleNext f $ bubbleDown f ns
          bubbleDown _ []     = []
          bubbleDown f (n:ns) = change f n $ bubbleDown f ns
              where change f m s@(n:ns) | f m n     = m:s
                                        | otherwise = n:m:ns
                    change _ m [] = [m]

逆の意味で典型的な例(?)ですね。大抵の言語では容易に実装出来るけどhaskellでは逆に大変な例ですね。ええ、実際、すんごい苦労しましたorz

-- 挿入ソート
insertSort _ [] = []
insertSort f (n:ns) = insert f n $ insertSort f ns
    where insert f n s@(m:ms) | f n m     = n:s
                              | otherwise = (m:) $ insert f n ms
          insert _ n [] = [n]

これは簡単でした。アルゴリズムが、ソート済みの集合に挿入していく形なので簡単に再帰の形に出来ます。ちなみにさりげなくアズパターンを使ってみました。

-- マージソート
mergeSort f ns = mergeCount f ns $ length ns
    where mergeCount _ _  0 = []
          mergeCount _ ns 1 = ns
          mergeCount f ns n = merge f ( before f ns n ) ( after f ns n )
               where before f ns n = mergeCount f ( take (div n 2) ns ) (div n 2)
                     after  f ns n = mergeCount f ( drop (div n 2) ns ) (n - (div n 2))
                     merge f sn@(n:ns) sm@(m:ms) | f n m     = (n:) $ merge f ns sm
                                                 | otherwise = (m:) $ merge f ms sn
                     merge _ [] ms = ms
                     merge _ ns [] = ns

簡単に出来るだろうと思ったのに割と苦労しました。抽象的には、ソート済みの二つの集合をマージしていく、ということで再帰の形には簡単に出来るんですが、面倒なのが半分にわけること。まあ速度考えなければlengthとtakeとdropで毎回計算しちゃってもいいんだけどね！

あといろいろ挑戦したんですが諦めましたorz 一番のネックはやはりリストなのでランダムアクセスが出来ないという点。