「ボゴソート」の版間の差分
表示
削除された内容 追加された内容
m ロボットによる 追加: es:Stupid sort, ru:Глупая сортировка |
|||
41行目: | 41行目: | ||
[[de:Bogosort]] |
[[de:Bogosort]] |
||
[[en:Bogosort]] |
[[en:Bogosort]] |
||
[[es:Stupid sort]] |
|||
[[it:Stupid sort]] |
[[it:Stupid sort]] |
||
[[nl:Bogosort]] |
[[nl:Bogosort]] |
||
46行目: | 47行目: | ||
[[pl:Bogosort]] |
[[pl:Bogosort]] |
||
[[pt:Bogosort]] |
[[pt:Bogosort]] |
||
[[ru:Глупая сортировка]] |
|||
[[sr:Глупи сорт]] |
[[sr:Глупи сорт]] |
||
[[tr:Saçma sıralama]] |
[[tr:Saçma sıralama]] |
2009年8月30日 (日) 21:20時点における版
ボゴソート (英語: bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。
ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、bogus(偽の)である。英語では、random sort, shotgun sort, monkey sort ともいう。
アルゴリズム
トランプを順に並べる場合を例にすると、次のようになる。
- トランプ52枚の束を放り投げて、ばらばらにする。
- 1枚ずつ無作為にすべてを拾い集める。
- ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。
カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。
疑似コード
function bogosort(array) while not is_sorted(array) array := random_permutation(array)
Perlによる実装
use List::Util 'shuffle';sub is_sorted{$_[$_-1]>$_[$_]&&return for 1..$#_;return 1}sub bogosort{@_=shuffle@_ until is_sorted@_;@_}
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!)となる。実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。
アルゴリズムの停止性は無限の猿定理により保証される。ただし計算機で擬似乱数を用いて実行すると、入力によっては停止しない場合がある。