ソート

Haskell のサンプルでクイックソートがよく挙げられている。こんな感じ。

quicksort []     =  []
quicksort (x:xs) =  quicksort [y | y <- xs, y < x]
                 ++ [x]
                 ++ quicksort [y | y <- xs, y >= x]

他のソートはどう書けばいいのだろう？というわけで、書いてみた。

実装

バブルソート

ソートといえばこれ。一番単純なアルゴリズムだけれども、Haskell で書くとクイックソートよりも複雑になっている。まあ、私の書いたコードがヘタレだというのもあるだろうが。

bubble_sort [] = []
bubble_sort x  = bubble_sort (take ((length x) - 1) (floating x)) ++ [last (floating x)]
  where
    floating [x] = [x]
    floating (x:xs) | x > head xs = [head xs] ++ floating (x:tail xs)
                    | otherwise   = [x] ++ floating xs

マージソート

好きなソート。同じ分割統治アルゴリズムを使用しているクイックソートより複雑になった。思ったんだけど、Haskell で書くと　for や while がないので、どんなアルゴリズムでも分割統治法を使わざるを得ないのか？

merge_sort []  = []
merge_sort [x] = [x]
merge_sort x   = merge (merge_sort (fst (split x))) (merge_sort (snd (split x)))
  where
    split x = splitAt ((length x) `div` 2) x
    merge []     []     = []
    merge (x:xs) []     = x:xs
    merge []     (y:ys) = y:ys 
    merge (x:xs) (y:ys) | x > y     = [y] ++ merge (x:xs) ys
                        | otherwise = [x] ++ merge xs (y:ys)

選択ソート

自分で書いたソートの中では一番単純。正式(?)な選択ソートだと要素の交換が発生しない箇所でも、この書き方だと交換が発生している。

import List

selection_sort []  = []
selection_sort [x] = [x]
selection_sort x   = [minimum x] ++ (selection_sort (delete (minimum x) x))

挿入ソート

な、長い。始めはもっと簡単に書けるかと思ったんだけど。一部クイックソートに似た箇所がある。
あと、ソートとは関係ないんだけど、見やすいインデントの方法はないかしら。

insertion_sort []     = []
insertion_sort (x:xs) = insertion [x] xs
  where
    insertion sorted rest | length rest <= 0 = sorted
                          | otherwise        = insertion
                                                  (
                                                    [n | n <- sorted, n <= head rest]
                                                    ++ [head rest]
                                                    ++ [n | n <- sorted, n > head rest]
                                                  )
                                                  (
                                                    tail rest
                                                  )

感想

ソートのアルゴリズムを知らない人が Haskell でソートを実装しようとすると、クイックソートのアルゴリズムを真っ先に思い浮かべるのではないだろうか。と、思えるぐらいにクイックソートはシンプルに実装されている。他の非関数型の言語では、こうは行かないのではないだろうか。総論 複数のプログラミング言語を学ぶ意義 | 日経 xTECH（クロステック） *1 で書かれている、

プログラミング言語も，同じように人間の思考に影響を与えます。

総論 複数のプログラミング言語を学ぶ意義 | 日経 xTECH（クロステック）

というのを実感した。
ただ、以下の記法を知っていなければならないが。

[y | y <- xs, y < x]

というか、この記法を学ばせる為にクイックソートがあるのでは？なんて。

*1:そういえば、この記事を見て、仕事では使わない言語も勉強してみようと思い始めたんだっけか。