>前から思っていたんだけど、 Haskell でいうと次に相当するクイックソート。
>
>qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (a:ax) = qsort [x | x <- ax, x < a] ++ [a] ++ qsort [x | x <- ax, x >= a]
>
>これって、記述の容易さ、シンプルさ、再帰的処理による分割統治法など、いろいろ見るべきところはあると思うんですが、はっきり言って全然速くないですよね。リスト内包表記
>
>するとシンプルかつ(比較的)効率的なのはマージソートなのかな、という気がします。ただ、リストを半分で割る、というところがちと面倒かな。長さを求めるとなると、やっぱり全体を読まないといけないので効率が良く無さげな。長さを与えておけば良いのかな。とすると、
>
>msort :: (Ord a) => [a] -> [a]
msort lst =
let len = length lst
in
mergesort len lst
where mergesort :: (Ord a) => Int -> [a] -> [a]
merge :: (Ord a) => [a] -> [a] -> [a]
mergesort 0 lst = []
mergesort 1 lst = [head lst]
mergesort n lst =
let n1 = n `div` 2
n2 = n - n1
l1 = lst
l2 = drop n1 lst
in merge (mergesort n1 l1) (mergesort n2 l2)
merge [] l2 = l2
merge l1 [] = l1
merge l1@(x:xs) l2@(y:ys) =
if x < y then x : merge xs l2
else y : merge l1 ys
>
>といったところですか。むむむ。思ったより長いなぁ。しかも、上のように書いた割には drop してるところがちょっとダサい気がする。やっぱ qsort は記述の簡潔さがウリなのですね。
>
>調べてみたら hugs/ghc の List.hs の sort はやっぱりマージソートですね。ちょっと長いですが、上に書いたのと方針は逆で、いったんリストの個々の要素を「それ自身のみを含むリスト」とみなし、どんどんマージしていってるみたいですね。そっちの方が速いかなぁ。
>
>ちなみに、 OCaml のソート(List.sort、List.fast_sort、List.stable_sort と3つも関数があるワリに実体はどれも同じ)はマージソートでした。こっちもやたら長いので省略しますが、方針は上に僕が書いたのと同じ。ただ、上手くリストが途中で2回反転するようにして、末尾呼出しにしています。
>
