クイックソート

Haskell でクイックソートを書くと、次のようになる。

qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]

あっけないほど短い。しかしそれだけでなく、クイックソートのアルゴリズムがよく分かるプログラムになっている。

1) 空リストは並べ替えても空リストである。
再帰的プログラムでは、停止の条件を決めておかないと、永遠に再帰状態が終わらなくなる。

2) リストの左端の要素を取り出す。
2行目の (x:xs) というパターンは、リストの先頭の要素を x に、それ以降のリストを xs にバインドすることを示す。つまり、左端の要素を取り出すということ。

3) x を取り出した残りの要素のリスト xs から、 x より小さい要素を集めて、elts_lt_x (elements less than x) という集合を作る。
[y | y <- xs, y < x] はリストの内包的な定義だが、集合の記法とそっくりに書くことができる。

4) x を取り出した残りの要素のリスト xs から、 x 以上の要素を集めて、elts_greq_x (elements greater than or equal x) という集合を作る。

5) x を一つ入れたリスト [x] の左に、elts_lt_x をソートしたものを連結し、[x] の右に elts_greq_x をソートしたものを連結する。
最初の1ステップでは、elts_it_x, [x], elts_greq_x という集合は確定するが、elts_lt_x や elts_greq_x はまだソートされていない。そこで qsort elts_it_x と qsort elts_greq_x が実行されるので [x] の両側の数列についても再帰的に作業が行われていく。
こういうアルゴリズムをそのまま記述しただけのようなプログラムが実際に動くというのが面白い。以前から、考えることを補助してくれるプログラム言語はないだろうかと思っていたが、現在のところ、Haskell がそれに一番近いような気がする。まだ慣れていないのでわからないが、何かアイディアを思いついたら先ず Haskell でプログラムして、それから、そのアイディアの足りないところをチェックしていくというような使い方ができるようになったら素敵だ。

追記

qsort プログラム別解

Prelude> let qsort [] = []; qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)
Prelude> qsort [2,9,7,3]
[2,3,7,9]
Prelude> qsort "hello"
"ehllo"

[PR]
by tnomura9 | 2009-08-09 05:22 | Haskell | Comments(0)
<< 直観的なプログラミング Haskell の情報源 >>