ボゴソート

ボゴソート

ボゴソートは、ソートアルゴリズムの中でも特に非効率なアルゴリズムとして知られています。平均的な計算時間はO(n×n!)であり、実用的な場面で使用されることはありません。安定ソートではなく、「bogo」という名前は「bogus（偽の、いんちきな）」に由来します。また、英語では、ランダムソート、ショットガンソート、モンキーソートなどと呼ばれることもあります。

アルゴリズム

ボゴソートのアルゴリズムは非常に単純です。例えば、トランプのカードを順番に並べる場合を例にすると、以下のようになります。

1. トランプ52枚の束をばらばらに放り投げます。
2. カードを1枚ずつ無作為に拾い集めます。
3. カードがソートされているかを確認します。もしソートされていなければ、手順1から3を繰り返します。

このアルゴリズムは、カードの束をひたすらシャッフルし続けて、偶然順番に並ぶのを待つようなものと考えることができます。ボゴソートの疑似コードは以下の通りです。


function bogosort(array)
while not is_sorted(array)
array := random_permutation(array)

計算時間と停止性

ボゴソートの計算時間は非常に長く、平均的な時間計算量はO(n×n!)となります。これは、n個の要素を並べ替えるのに必要な操作量がnであり、その操作を繰り返す回数の期待値がn!であるためです。n!は、全ての並びのうち正しい並びである割合の逆数です。もし同じ要素が含まれている場合は、正しい並びの個数をaとすると、計算量はO(n×n!/a)となります。ただし、これは大まかな議論であり、並びを判定する計算量などは考慮していません。

理論的には、ボゴソートの停止性は無限の猿定理に依存することになります。無限の猿定理とは、「無限の時間があれば、猿がランダムにタイプライターを叩き続ければ、いつかシェイクスピアの作品を打ち出すことができる」というものです。しかし実際には、コンピュータで実行した場合、擬似乱数の偏りによって停止しない可能性もあります。

関連アルゴリズム

ボゾソート

ボゾソートも乱数を利用したソートアルゴリズムの一つです。リストがソートされていない場合、ランダムに2つの要素を選んで入れ替え、リストがソートされているかどうかを調べます。ボゾソートの実行時間の解析は複雑ですが、H. Gruberの研究により実行時間の見積もりが示されています。

その他

ジャーゴンファイルの「bogo-sort」の項では、ボゴソートの壮大なバリエーションとして、量子力学的に全ての選択肢を並列で試行し、正しい結果のみを取り出すというアイデアが紹介されています。これは、ボゴソートの非効率さを逆手に取ったユーモラスな発想と言えるでしょう。

関連項目

ラスベガス法

参考文献

H. Gruber, An Analysis of Perversely Awful Randomized Sorting Algorithms, 2007.
* ジャーゴンファイル

もう一度検索