ボゴソート
(ボゾソート から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/06/13 18:33 UTC 版)
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。
|
- ^ 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
- 1 ボゴソートとは
- 2 ボゴソートの概要
- 3 関連アルゴリズム
ボゾソート
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/06/13 18:33 UTC 版)
ボゾソートも乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithmsに実行時間の見積もりが示されている。
※この「ボゾソート」の解説は、「ボゴソート」の解説の一部です。
「ボゾソート」を含む「ボゴソート」の記事については、「ボゴソート」の概要を参照ください。
- ボゾソートのページへのリンク