Bogobogosortについて
遅いソートアルゴリズム
Bogobogosortという、名前からして恐ろしいソートアルゴリズムを知ったきっかけはtodo314さんのこのPostからでした。
ボゴソートより計算量の大きいソートアルゴリズムってあるのかしら。論文あるか調べてみようかな。
遅いソート方法というと、どこまでの無駄が許されるのかという話になってくる気もしますが、例えば以下のURLではkinabaさんが情報量が0である比較を除いた計算量について考察されてます。
今回のようにボゴソートのO(n*n!)がソートアルゴリズムとして許容されるとなると、結構なんでもありな気がしてきます。
まず、よく知られているソートアルゴリズムでボゴソートと同じくらいの計算量を持つものには
- ボゴソート：ソートされたものが見つかるまでrandom_shuffle
- ボゾソート：ソートされるまでランダムに選んだの2つの要素を交換
- permutation sort ：順番が揃うまでnext_permutation
などがあります。
その時のTLでみたアルゴリズムではstacさんの
1/2の確率でランダムにnext or prev permutationを行う
というアイデアが秀逸でした。ランダムウォークみたいな話です。計算量はO((n!)^2)辺りになりそう。
Bogobogosort
そうしていると、todo314さんからbogobogosortがあるとのPostが。気になる。
Bogobogosortというソートアルゴリズムがある。ぱない。
詳細はこのサイトより。以下はその抄訳と説明。英語に抵抗ない人はリンク先を読んだ方が良いと思います。
DM's Esoteric Programming Languages - Bogobogosort
Bogobogosortは、有名なbogosortを基にしたソートアルゴリズムで、これを理解するにはまずボゴソートの細かい部分を理解する必要があります。
- リストがソートされているかチェックし、されていれば停止、違えばStep2へ
- リストをランダムに並び替える
- Step1に戻る
比較が線形時間、ループが平均n!/2回で、計算量O(n*n!)という、非常に効率的なアルゴリズムです。
Bogobogosortの特徴はリストがソートされているかどうかのチェックに再帰を用いることです。再帰というのは常にgoodでcoolですから。
Bogobogosortではボゴソートのチェックの部分を以下のようにします。
- 元のリストをコピーしたリストを作成します。
- コピーしたリストの先頭からn-1要素をbogobogosortを使ってソートします。
- コピーのn番目の要素がn-1個の要素の最大値より大きければ、コピーはソートされている。違えばコピーの順番をシャッフルし、もう一度Step2からやり直す。
- ソートされたコピーが元のリストと同じかどうか比較する。
これをボゴソートのStep1で行われるようにしたものがbogobogosortです。
C++での実行結果は
n Time (seconds)
1 0.0000
2 0.0000
3 0.0008
4 0.0054
5 0.0745
6 450
7 一晩中動かしたが終了せず
コードが載ってないので書いてみました。
- bogosortのC++による実装
- bogobogosortのC++による実装
n=6でも終わらないんだけど...あれれ?
bogobogosortぐらいになると乱数の使用回数が馬鹿みたいに多いので、乱数生成にMTとか使った方が良かったのかもしれません。
計算量がアッカーマン関数程度になるような面白いものを見つけたい。
