「ボゴソート」の版間の差分
表示
削除された内容 追加された内容
m ロボットによる 追加: ru:Глупая сортировка |
m Bot: テンプレートの差替え (WP:BOTREQ#スタブテンプレート修正依頼) |
||
23行目: | 23行目: | ||
ただし[[計算機]]で[[擬似乱数]]を用いて実行すると、入力によっては停止しない場合がある。 |
ただし[[計算機]]で[[擬似乱数]]を用いて実行すると、入力によっては停止しない場合がある。 |
||
{{ |
{{Computer-stub}} |
||
[[Category:ソート|ほこそおと]] |
[[Category:ソート|ほこそおと]] |
||
2008年1月28日 (月) 03:43時点における版
ボゴソートは、ソートのアルゴリズムの一つ。 平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。 安定ソートではない。
アルゴリズム
トランプを順に並べる場合を例にすると、次のようになる。
- トランプ52枚の束を放り投げて、ばらばらにする。
- 1枚ずつ無作為にすべてを拾い集める。
- ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。
カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えても良い。
疑似コード
function bogosort(array) repeat array := random_permutation(array) until is_sorted(array)
計算時間および停止性
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる。 実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。
アルゴリズムの停止性は無限の猿定理(en:Infinite monkey theorem)により保証される。 ただし計算機で擬似乱数を用いて実行すると、入力によっては停止しない場合がある。