Haskell でバブルソート

Haskell でバブルソートをプログラムしてみた。Haskell でバブルソートのような効率の悪いソートをプログラムしてもあまり意味が無いので、アルゴリズムが分かるようにしてみた。バブルソートのアルゴリズムは次のようなものだ。

バブルソートの基本的なアイディアとしては、リストの全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替えるという方法だ。これをn-1回繰り返すと、全ての要素を整列することができる。

次のプログラムは、このアルゴリズムを眼に見えるようにしてみたものだ。関数 sweep はリスト xs の全ての要素を全て操作してとなりある要素が逆順の場合は入れ替える。関数 bubble はその間の過程を全て列挙する。

sweep [x] = [x]
sweep (x:y:rest)
  |x > y = y : sweep (x:rest)
  |otherwise = x : sweep (y:rest)

bubble xs = take (length xs) $ iterate sweep xs

実行例

Main> sweep [3,2,1]
[2,1,3]
Main> sweep [2,1,3]
[1,2,3]

一回のsweep毎に大きい数が右の方へ移動する。bubble を実行すると次のようになる。


Main> bubble [5,4,2,1,3]
[[5,4,2,1,3],[4,2,1,3,5],[2,1,3,4,5],[1,2,3,4,5],[1,2,3,4,5]]

一回の sweep 毎に大きい数が右端の方へ沈殿していって、最終的に整列するのが分かる。Haskell を使うと、アルゴリズムを簡単に可視化することができるので便利だ。

ところで、バブルソートのアルゴリズム通りに Haskell でプログラムすると次のようになる。

bsort [x] = [x]
bsort xs = bsort (init (sweep xs)) ++ [last (sweep xs)]

アルゴリズムのアイディアはよくわかるが、オーバーヘッドが大きく、C言語などでプログラムしたときのコンパクトさは感じられない。ループや代入を排除したために、アルゴリズムそのものの表現が直観的にできるようになったが、その分、単純なアルゴリズムを表現するためのオーバーヘッドが生じてしまった。

Haskell でプログラムしていて一番嬉しいのは、文字列の処理をする感覚で、アルゴリズムを直接コードに落としていけるような感覚だ。

どうしてそういう感覚が生まれてくるのかというと、Haskell ではループが使えないため、必然的にプログラムがリストを切ったり繋いだりというようなイメージ的な処理や、再帰関数の定義で行わざるを得なくなる。ところが、リストを切ったり繋いだりというイメージ的な操作や、再帰関数で繰り返しの構造の本質を取り出すやり方は、アルゴリズムそのものと親和性がいいようだ。

ループが書けないことや、全てを関数で表現しなければならないことや、純粋関数とIO処理のような副作用のある関数の世界が厳格に区分されていることは、Haskell の制約だが、そのことが、かえってイメージ的なアルゴリズムをダイレクトに表現できる要因となっているのが面白い。


今日の Haskell
Main> take 10 (iterate (2*) 1)
[1,2,4,8,16,32,64,128,256,512]

iterate は第1引数の関数を第2引数に繰り返し適用させた無限リストをつくる。
[PR]
by tnomura9 | 2010-12-06 21:21 | Haskell | Comments(0)
<< Ruby Haskell 化計画 英語学習に文法は必要か。 >>