ボゴソート

ボゴソート

クラス	ソート
データ構造	配列
最悪計算時間	${\displaystyle O(\infty )}$
最良計算時間	${\displaystyle O(n)}$
平均計算時間	${\displaystyle O(n\cdot n!)}$
最悪空間計算量	${\displaystyle O(n)}$

ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"^[1]に由来する。

英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。

アルゴリズム[編集]

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

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

カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよい。

疑似コード[編集]

function bogosort(array)   while not is_sorted(array)     array := random_permutation(array) 

Perlによる実装[編集]

use List::Util 'shuffle'; sub is_sorted {   for (1 .. $#_) {     return 0 if ($_[$_ - 1] > $_[$_]);   }   return 1; } sub bogosort {   until (is_sorted(@_)) {     @_ = shuffle @_;   }   return @_; } 

C++による実装[編集]

#include <algorithm> #include <random> template <class RandomIter> void bogosort( RandomIter first, RandomIter last ) {   while( !std::is_sorted( first, last ) )     std::shuffle( first, last, std::default_random_engine() ); } 

計算時間および停止性[編集]

すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる（1回の並べ直しに必要な操作量が n 、それを繰り返す回数の期待値のオーダーが n! ）。n! は、全ての並びのうち、正しい並びである割合である 1 / n! の逆数であり、等しい要素が含まれている場合、それによる正しい並びの個数が a とすると、O(n×n! / a) となる。以上はかなりおおざっぱな議論で、たとえば並びを判定する計算量を考慮していない。

理論的にはまた、このアルゴリズムの停止性は無限の猿定理に依ることになる。なお実際的には、現実のコンピュータで実施した場合、擬似乱数のせいで停止しないこともあり得る。

関連アルゴリズム[編集]

ボゾソート[編集]

ボゾソートも乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithms^[2]に実行時間の見積もりが示されている。

その他[編集]

ジャーゴンファイルの「bogo-sort」の項^[3]では「A spectacular variant」が提案されているとして、「量子的に」全ての選択を並列に行い、正しかったもののみを結果として取り出す、というアイディアが示されている。

関連項目[編集]

• ラスベガス法

参考文献[編集]

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート
選択ソート	選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート
挿入ソート	挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート
マージソート	マージソート 多層マージソート ストランドソート
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート
混成ソート	ティムソート イントロソート Jソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート エラーソート
カテゴリ