|
ボゴソート
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。 英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。 アルゴリズムトランプを順に並べる場合を例にすると、次のようになる。
カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよい。 疑似コード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」が提案されているとして、「量子的に」全ての選択を並列に行い、正しかったもののみを結果として取り出す、というアイディアが示されている。 関連項目参考文献
Information related to ボゴソート |
||||||||||||||||||||||||||||||||||||
