ボゴソート

ボゴソート（英： bogosort, bogo-sort, bogo sort）とは、ソートアルゴリズムの一種である。

概要

ソートの対象をトランプとすると、

1. トランプをシャッフルする。
2. きちんと順番になってるかどうかを調べる。
3. 順番になっていれば終了。なっていなければ1に戻る。

というこの上なく漢らしい冗談のようなソートアルゴリズム。ちなみにボゴ（bogo- < bogus）とは「偽、いんちき」といった意味であり、冗談のようなどころか本当に冗談である。

無限の猿定理により必ずソートできることが保証されてはいるものの、気が遠くなるほどの時間がかかることも事実で、平均計算時間は O(n×n!) 、最悪計算時間は ∞ 。数あるソートアルゴリズムの中でも最低の性能である。
このため、stupid sort, slowsort, monkey sort （以上、サルでもできる愚鈍なソート）、random sort, shotgun sort （以上、下手な鉄砲も数撃ちゃ当たるソート）とも呼ばれている。

しかしながら、最良計算時間は O(n) という、クイックソートを超えるほぼ理論値であるため、今後量子コンピュータクラスの並列処理が可能になればクイックソートを抑えて脚光を浴びるとか浴びないとか言われている隠れた有望株でもある。

実装自体はランダムにブチ撒けるだけでありそれほど難しくないように思えるが、乱数というコンピュータにとって苦手な分野を扱うために性能のいい乱数発生器が必要不可欠であり、乱数発生器に性能の大部分を依存するので理論的にはまだまだ効率追求の余地がある。

関連動画

　

関連商品

ボゴソートに関するニコニコ市場の商品を紹介してください。

関連コミュニティ

ボゴソートに関するニコニコミュニティを紹介してください。

関連項目

• ソート
• アルゴリズム
• 無限の猿定理
• BogoMips