「ボゴソート」の版間の差分
m r2.7.1) (ロボットによる 追加: ca:Bogosort |
|||
(13人の利用者による、間の20版が非表示) | |||
8行目: | 8行目: | ||
|space=<math>O(n)</math> |
|space=<math>O(n)</math> |
||
|optimal=No |
|optimal=No |
||
}} |
|||
}}'''ボゴソート''' ([[英語]]: bogosort) は、[[ソート]]の[[アルゴリズム]]の一つ。平均的な計算時間は[[ランダウの記号|O]](n×n!)で、非常に効率の悪いアルゴリズムとして知られている。[[安定ソート]]ではない。 |
|||
'''ボゴソート''' (bogosort) は、[[ソート]]の[[アルゴリズム]]の一つ。平均的な計算時間は[[ランダウの記号|O]](n×n!)で、非常に効率の悪いアルゴリズムとして知られている。[[安定ソート]]ではない。「bogo」は、"bogus"<ref>http://catb.org/~esr/jargon/html/B/bogus.html</ref>に由来する。<!--ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、bogus(偽の)である。--><!-- ← quantum bogodynamics( http://catb.org/~esr/jargon/html/Q/quantum-bogodynamics.html )のようですが、ボゴソートと、冗談理論である quantum bogodynamics に、特段のつながりは無いように見受けられます--> |
|||
英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、[[無限の猿定理]]を指しているかもしれない。 |
|||
ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、bogus(偽の)である。英語では、random sort, shotgun sort, monkey sort ともいう。 |
|||
==アルゴリズム== |
==アルゴリズム== |
||
17行目: | 18行目: | ||
#1枚ずつ[[ランダム|無作為]]にすべてを拾い集める。 |
#1枚ずつ[[ランダム|無作為]]にすべてを拾い集める。 |
||
#ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 |
#ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 |
||
カードをシャッフルし続けて |
カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよい。 |
||
===疑似コード=== |
===疑似コード=== |
||
25行目: | 26行目: | ||
===Perlによる実装=== |
===Perlによる実装=== |
||
< |
<syntaxhighlight lang="perl"> |
||
use List::Util 'shuffle'; |
use List::Util 'shuffle'; |
||
sub is_sorted { |
sub is_sorted { |
||
39行目: | 40行目: | ||
return @_; |
return @_; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
===C++による実装=== |
===C++による実装=== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <algorithm> |
#include <algorithm> |
||
#include <random> |
|||
template <class |
template <class RandomIter> |
||
void bogosort(InputIter first, InputIter last){ |
|||
void bogosort( RandomIter first, RandomIter last ) |
|||
{ |
|||
while( !std::is_sorted( first, last ) ) |
|||
std::shuffle( first, last, std::default_random_engine() ); |
|||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==計算時間および停止性== |
==計算時間および停止性== |
||
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる |
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる(1回の並べ直しに必要な操作量が n 、それを繰り返す回数の期待値のオーダーが n! )。n! は、全ての並びのうち、正しい並びである割合である 1 / n! の逆数であり、等しい要素が含まれている場合、それによる正しい並びの個数が a とすると、O(n×n! / a) となる。以上はかなりおおざっぱな議論で、たとえば並びを判定する計算量を考慮していない。 |
||
アルゴリズム |
理論的にはまた、このアルゴリズムの停止性は[[無限の猿定理]]に依ることになる。なお実際的には、現実の[[コンピュータ]]で実施した場合、[[擬似乱数]]のせいで停止しないこともあり得る。 |
||
==関連アルゴリズム== |
==関連アルゴリズム== |
||
===ボゾソート=== |
===ボゾソート=== |
||
'''ボゾソート'''も乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithms<ref name="Fun07">H. Gruber, M. Holzer and O. Ruepp: ''[http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms]'', 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.</ref>に実行時間の見積もりが示されている。 |
'''ボゾソート'''も乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithms<ref name="Fun07">H. Gruber, M. Holzer and O. Ruepp: ''[http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms]'', 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.</ref>に実行時間の見積もりが示されている。 |
||
==その他== |
|||
[[ジャーゴンファイル]]の「bogo-sort」の項<ref>http://catb.org/~esr/jargon/html/B/bogo-sort.html</ref>では「A spectacular variant」が提案されているとして、「量子的に」全ての選択を並列に行い、正しかったもののみを結果として取り出す、というアイディアが示されている。 |
|||
==関連項目== |
==関連項目== |
||
[[ラスベガス法]] |
*[[ラスベガス法]] |
||
==参考文献== |
==参考文献== |
||
{{reflist}} |
|||
<references/> |
|||
{{Computer-stub}} |
|||
{{ソート}} |
{{ソート}} |
||
⚫ | |||
⚫ | |||
[[ca:Bogosort]] |
|||
[[ |
[[Category:ソート]] |
||
[[Category:コンピュータ・ユーモア]] |
|||
[[de:Bogosort]] |
|||
[[en:Bogosort]] |
|||
[[es:Stupid sort]] |
|||
[[fa:مرتبسازی بوگو]] |
|||
[[fr:Tri stupide]] |
|||
[[it:Stupid sort]] |
|||
[[nl:Bogosort]] |
|||
[[no:Bogosortering]] |
|||
[[pl:Bogosort]] |
|||
[[pt:Bogosort]] |
|||
[[ru:Bogosort]] |
|||
[[sr:Глупи сорт]] |
|||
[[tr:Saçma sıralama]] |
|||
[[uk:Сортування Бого]] |
|||
[[zh:Bogo排序]] |
2020年7月5日 (日) 22:48時点における最新版
クラス | ソート |
---|---|
データ構造 | 配列 |
最悪計算時間 | |
最良計算時間 | |
平均計算時間 | |
最悪空間計算量 |
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。
英語では、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 {
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!)となる(1回の並べ直しに必要な操作量が n 、それを繰り返す回数の期待値のオーダーが n! )。n! は、全ての並びのうち、正しい並びである割合である 1 / n! の逆数であり、等しい要素が含まれている場合、それによる正しい並びの個数が a とすると、O(n×n! / a) となる。以上はかなりおおざっぱな議論で、たとえば並びを判定する計算量を考慮していない。
理論的にはまた、このアルゴリズムの停止性は無限の猿定理に依ることになる。なお実際的には、現実のコンピュータで実施した場合、擬似乱数のせいで停止しないこともあり得る。
関連アルゴリズム[編集]
ボゾソート[編集]
ボゾソートも乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithms[2]に実行時間の見積もりが示されている。
その他[編集]
ジャーゴンファイルの「bogo-sort」の項[3]では「A spectacular variant」が提案されているとして、「量子的に」全ての選択を並列に行い、正しかったもののみを結果として取り出す、というアイディアが示されている。
関連項目[編集]
参考文献[編集]
- ^ http://catb.org/~esr/jargon/html/B/bogus.html
- ^ H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.
- ^ http://catb.org/~esr/jargon/html/B/bogo-sort.html