ボゴソート
ボゾソートも乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithmsに実行時間の見積もりが示されている。
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"に由来する。
英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。