ボゴソート

ボゴソート

クラス	ソート
データ構造	配列
最悪計算時間	$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!)となる。実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。

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

関連アルゴリズム

ボゾソート

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

関連項目

• ラスベガス法