ボゴソート

ボゴソート

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

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

ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、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>
template <class InputIter>
void bogosort(InputIter first, InputIter last){
  while(!std::is_sorted(first, last))
    std::random_shuffle(first, last);
}

計算時間および停止性

すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる。実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。

アルゴリズムの停止性は無限の猿定理により保証される。ただし計算機で擬似乱数を用いて実行すると、入力によっては停止しない場合がある。

関連アルゴリズム

ボゾソート

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

関連項目

ラスベガス法