「ボゴソート」の版間の差分
表示
削除された内容 追加された内容
→疑似コード: はじめから順番になっていたときに捨ててしまうのはもったいない |
Hatukanezumi (会話 | 投稿記録) m 翻訳ずみリンクトル; sty; 用字 |
||
1行目: | 1行目: | ||
'''ボゴソート'''は、[[ソート]]の[[アルゴリズム]]の一つ。 |
'''ボゴソート'''は、[[ソート]]の[[アルゴリズム]]の一つ。平均的な計算時間は[[ランダウの記号|O]](n×n!)で、非常に効率の悪いアルゴリズムとして知られている。[[安定ソート]]ではない。 |
||
平均的な計算時間は[[ランダウの記号|O]](n×n!)で、非常に効率の悪いアルゴリズムとして知られている。 |
|||
[[安定ソート]]ではない。 |
|||
==アルゴリズム== |
==アルゴリズム== |
||
8行目: | 6行目: | ||
#1枚ずつ[[ランダム|無作為]]にすべてを拾い集める。 |
#1枚ずつ[[ランダム|無作為]]にすべてを拾い集める。 |
||
#ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 |
#ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 |
||
カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えても |
カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。 |
||
===疑似コード=== |
===疑似コード=== |
||
16行目: | 14行目: | ||
==計算時間および停止性== |
==計算時間および停止性== |
||
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる。 |
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる。実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。 |
||
実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。 |
|||
アルゴリズムの[[チューリングマシンの停止問題|停止性]]は[[無限の猿定理]] |
アルゴリズムの[[チューリングマシンの停止問題|停止性]]は[[無限の猿定理]]により保証される。ただし[[計算機]]で[[擬似乱数]]を用いて実行すると、入力によっては停止しない場合がある。 |
||
ただし[[計算機]]で[[擬似乱数]]を用いて実行すると、入力によっては停止しない場合がある。 |
|||
{{Computer-stub}} |
{{Computer-stub}} |
2008年10月5日 (日) 05:35時点における版
ボゴソートは、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。
アルゴリズム
トランプを順に並べる場合を例にすると、次のようになる。
- トランプ52枚の束を放り投げて、ばらばらにする。
- 1枚ずつ無作為にすべてを拾い集める。
- ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。
カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。
疑似コード
function bogosort(array) while not is_sorted(array) array := random_permutation(array)
計算時間および停止性
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる。実際の計算時間は、等しい要素が含まれているか、そしてそれらがどのくらいの頻度で含まれているかに依存する。
アルゴリズムの停止性は無限の猿定理により保証される。ただし計算機で擬似乱数を用いて実行すると、入力によっては停止しない場合がある。