ボゴソート

今晩は。

面白いアルゴリズムをちまちま紹介しようかなということで、まずはソートについて。

ソートは非常に重要なアルゴリズムなので、かつてから研究されていて、非常に多くのものがあります。

大抵の実用的なアルゴリズムの計算時間は、

平均計算時間:O(n*log(n))
最悪計算時間:O(n^2)

のような感じですが、こんなアルゴリズムもあります。

ボゴソート
平均計算時間:O(n*n!)
最悪計算時間:∞

そして、安定性なしという素晴らしきソートアルゴリズムです。

トランプを順に並べる場合を例にすると、次のようになる。

1.トランプ52枚の束を放り投げて、ばらばらにする。
2.1枚ずつ無作為にすべてを拾い集める。
3.ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。

カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えても良い。

「ボゴソート」『フリー百科事典　ウィキペディア日本語版』（http://ja.wikipedia.org/）。2008年7月12日21時01分（日本時間）現在での最新版を取得。

という訳で、紹介するだけなのもなんなので、計測してみました。

ボゴソート計測結果

要素数[個]	試行回数[回]	平均時間(指数)[sec]	平均時間(小数)[sec]
2	20,000,000	1.55E-6	0.00000155
3	20,000,000	2.20E-6	0.00000220
4	20,000,000	5.53E-6	0.00000553
5	10,000,000	2.45E-5	0.0000245
6	1,000,000	1.28E-4	0.000128
7	100,000	9.38E-4	0.000938
8	20,000	7.17E-3	0.00717
9	1,000	7.02E-2	0.0702
10	100	6.53E-1	0.653
11	100	7.11E+0	7.11

CPU:Intel(R) Pentium(R)4 CPU 3.20 GHz
平均時間は3桁目で四捨五入しています。

要素数につれて、驚く程ソート時間が増えているのが明白に分かります。
上でO(n*n!)だと書きましたが、あまりそれに沿ってないような気がします。クヌースのシャッフル出ないこと原因かもしれないし、ランダム性が高いので、試行回数が足りない所為かも知れません。

他にも特殊なソートがあるので、ちょこまかと紹介していこうと思います。