ボゴソート

ボゴソート

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

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

英語では、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に実行時間の見積もりが示されている。

その他

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

関連項目

• ラスベガス法