たくさん学びました！世界で最も遅いソートアルゴリズム！

今日は、世界で最も遅いソートアルゴリズムである Bogo ソートについてお話ししたいと思います。

では、早速擬似コードを見てみましょう。

 int bogo_sort(int& arr[], int n){
        while( false == is_sorted(arr[n])){
                ランダムシャッフル(arr[n]);
        }
        0を返します。
 }

このゲームがモンキーソーティングと呼ばれる理由は、猿がキーボードをランダムに長く叩くと、シェイクスピアの詩を入力できるという喩えから来ています。

疑似コードを見ると、中心となる考え方が次のとおりであることが簡単にわかります。

（１）ソートする配列が順序どおりであるかどうかを判定する。順序どおりであれば、完了したソートを返す。

（２）配列が乱れている場合は、配列をランダムにシャッフルする。

（３）（１）を繰り返す。

実行時間が十分に長く、ランダム回数が十分に長い限り、常にソートされた結果が得られます。これは世界で最も遅いソートアルゴリズムとして知られています。

それで、質問は、このソートの用途は何なのかということです。

私が思いつくのは、大学のアルゴリズムの授業で時間計算量の導出演習をすること、就職面接で時間計算量の計算を問われること、あるいは自分の知性を誇示するための話題くらいです。それ以外は、何の役にも立たないように思えます。

このソートアルゴリズムの時間計算量はどれくらいですか?

簡単に分析してみましょう。

n 個の要素がランダムにシャッフルされた n! の組み合わせがあります。

• ソートが成功する確率は p1 = 1/n! であり、ソートが失敗する確率は p2 = 1-p1 です。

• 2 回のソートが成功する確率は p2*p1 です。ナレーション: 1 回目は失敗し、2 回目は成功しました。

• 3 回のソートが成功する確率は p2^2*p1 です。ナレーション: 最初の 2 回は失敗し、3 回目は成功しました。

• …

• k 回のソートが成功する確率は p2^(k-1)*p1 です。ナレーション: 最初の k-1 回は失敗し、k 回目は成功しました。

• …

したがって、ソートが成功すると予想される平均数は次のようになります。

E(X) = 1 回 * 1 回の成功の確率 + 2 回 * 2 回の成功の確率 + 3 回 * 3 回の成功の確率 + ... + k 回 * k 回の成功の確率 + ...

今すぐ：

最後に、大学で学んだ無限級数の数学的知識に基づくと、その時間計算量は O(n*n!) であり、階乗レベルのアルゴリズムであることが「簡単に」わかります。

[この記事は51CTOコラムニスト「58 Shen Jian」によるオリジナル記事です。転載については原作者までお問い合わせください。]

この著者の他の記事を読むにはここをクリックしてください