【絶対使うな！】ボゴソートとは？計算量は？解説してみた

これまで、色々なソートアルゴリズムを解説してきた。

単純なソートアルゴリズムであるバブル、選択、挿入ソート。

高速なソートアルゴリズムであるクイック、マージ、ヒープソート。

また、挿入ソートの改良であるシェルソートも。

ただ、ソートはこれだけではない。

今回は、ネタとしてボゴソートを解説しよう。

…いや、解説するほどのこともないのだが。

とにかく、一つだけ言えることは、このボゴソートだけは絶対に使わないでほしい。

シノ

一応存在するってことで紹介だけするよ！

ボゴソート

ボゴソートの考え方は非常に簡単だ。

まず、データをランダムに並び替える。

そして、それがソート済みかどうかを確認する。

これを、ソートが完了するまで繰り返す。

以上。

…もはやネタなソートだ。

ボゴソートの計算量

こんなソートだが、計算量も当然しっかり算出されている。

このボゴソートの計算量は、\(O(n \times n!)\)だ。

\(n!\)は階乗で、1からnまでを全て掛け合わせた数になる。

例えば、3!なら\(3 \times 2 \times 1 = 6\)、5!なら\(5 \times 4 \times 3 \times 2 \times 1 = 120\)といった感じ。

\(n^2\)とは比較にならないレベルで遅いことが分かるだろう。

ボゴソートのサンプルプログラム

提示する意味があるかは分からないが、念のためサンプルプログラムを提示しておこう。

先に注意だが、これに渡すデータは多くても10個程度にしておこう。

あまり大きい配列を渡すと、なかなかソートが終わらず表示したページが固まってしまう。

それほどまでに遅いソートということだ。

function BogoSort(data){
    while(true){
        shuffle(data);
        if(check(data)){
            break;
        }
    }
}

function shuffle(data){
    for(let i = data.length - 1; i >= 0; i--){
        let rand = Math.floor(Math.random() * (i + 1));
        let tmp = data[i];
        data[i] = data[rand];
        data[rand] = tmp;
    }
}

function check(data){
    let n = data.length;

    for(let i = 0; i < n - 1; i++){
        if(data[i] > data[i + 1]){
            return false;
        }
    }
    return true;
}

ランダムに並び替える部分と、チェックする部分を関数に切り出してみた。

shuffle()関数が、配列をランダムに並び替える処理。

check()関数が、ソート済みかどうかを判定する処理だ。

オマケで、要素数が5個から9個のときに、何回くらいシャッフルをしているか確認してみよう。

1000回ずつソートし、その平均を取ると、以下のようになった。

大雑把にだが、データ数の階乗くらいになっている。

これの1回ごとに比較回数が加わるので、計算量も\(O(n \times n!)\)になるのがなんとなく分かると思う。

おわりに

今回は、ボゴソートについて解説した。

完全にネタのソートだ。

繰り返しになるが、絶対にこのソートは使わないようにしよう。