要素同士を比較しない！？ビンソートを解説！

これまで解説してきたソートは、全て要素同士の比較を行うソートだった。

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

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

そして、挿入ソートの改良であるシェルソートも。

もう一個ネタで解説したボゴソートだって、一応比較を行っている。

しかし、その比較を行わずしてソートする方法もあるのだ。

今回から、そんな比較を行わないソートを解説していこう。

まずは、ビンソートと呼ばれるソートを見ていく。

データに条件がついてしまうが、その中では非常に効力を発揮するソートだ。

シノ

クイックソートよりも速くソートできるよ！

条件を満たしているならこれも検討してみよう！

ビンソート

先に、今回のビンソートでは、データに条件がある。

以下の二つだ。

• 要素が整数(自然数)
• 要素に重複がない

このほか、より高速にソートするなら、並び替えるデータの最大値が分かっているとなおよしだ。

理由は、ソートの内容を見ればわかる。

というわけで、ビンソートの解説に入ろう。

まず、データが取り得る値全てに対応する箱を用意する。

そして、データが対応する箱の中に、データを入れていく。

これを全て入れ終えたら、小さい順に取り出せば、ソート完了だ。

では、具体例で見ていこう。

まず、並び替えるデータは以下の通りとする。

また、データは大きくても10だと分かっているとしよう。

では、まず箱を用意する。

この箱のことを英語でbinと呼ぶので、そのままそれを配列にしてしまおう。

なお、binを使うからビンソートだ。

次に、データの添え字のところに、フラグを立てていこう。

データは7, 4, 2, 8, 1なので…

こうなる。

あとは、先頭から順番にありのところをデータとして持って来ればいいので…

これで、ソートが完了だ。

最大値が分かっていると、そこまで箱を用意すれば十分なので、効率よくソートができる。

これが、最大値が分かっていた方がいい理由だ。

また、重複があるとこの方法では上手くいかないことも分かると思う。

今回はYESorNOの二択で箱に入れているので、これだと複数の表現ができない。

ビンソートの計算量

なんと、驚きの計算量\(O(n)\)だ。

と書いたが、\(O(n \log(n))\)と大きく変わるかと言われると、実はそこまで劇的な変化ではない。

また、状況によってはやはり他のソートの方が良かったりもするので、それは状況を見ながら判断してほしい。

計算量が\(O(n)\)になる理由も解説しておこう。

まず、データ数をn、用意する箱の大きさをmとする。

最初に、データを箱に入れるときにn回。

取り出すときに、箱の大きさだけチェックするのでm回。

というわけで、計算量は\(O(n + m)\)となる。

このとき、データ量と比べて箱の大きさがそんなに大きくなければ…例えば、データ数の大きくても2倍程度の箱を常に用意できれば、計算量は\(O(n + 2n) = O(3n) = O(n)\)となる。

しかし、最大値が分からず、あまりに大きくしてしまうと、今度は\(O(m)\)となってしまう。

このようなときは、大人しく別のソートを使うようにしよう。

そのほか、これには大きめの作業用領域が必要という欠点もある。

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

恒例のサンプルプログラムだ。

いつもと同じく、JavaScriptで組んでいる。

function BinSort(data, data_max){
    let bin = [];

    for(let i = 0; i <= data_max; i++){
        bin[i] = false;
    }

    for(let i = 0; i < data.length; i++){
        bin[data[i]] = true;
    }

    let i = 0;
    for(let j = 0; j <= data_max; j++){
        if(bin[j]){
            data[i] = j;
            i++;
        }
    }
}

まず、引数としてソートするデータ自体と、そのデータがこれ以上にはならないという値を受け取るようにしている。

上でも解説した通り、この値があまりに大きいと効率が悪くなるので注意しよう。

そして、一つ目のfor文でbinの初期化だ。

次のfor文で、データの部分にフラグを立てている。

最後のfor文でbinの先頭からチェックしていき、trueならその添え字を元の配列に戻す、ということをしている。

おわりに

今回は、要素同士を比較しないソートということで、一つ目のビンソートを紹介した。

しかし、条件がちょっと厳しいだろう。

というわけで、次回は重複したデータもソートできる分布数え上げソートを解説する。

今回の内容をちょこっと変えるだけで実現できてしまう。

余力があれば、どのように変えるかもちょっと考えてみよう。