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

アルゴリズムとデータ構造講座

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

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

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

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

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

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

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

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

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

シノ
シノ

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

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

スポンサーリンク

ビンソート

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

以下の二つだ。

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

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

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

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

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

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

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

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

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

i01234
data[i]74281
ソートするデータ

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

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

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

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

i012345678910
bin[i]なしなしなしなしなしなしなしなしなしなしなし
箱の中身

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

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

i012345678910
bin[i]なしありありなしありなしなしありありなしなし
箱の中身2

こうなる。

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

i01234
data[i]12478
箱から取り出したデータ=ソート結果

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

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

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

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

今回は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ならその添え字を元の配列に戻す、ということをしている。

おわりに

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

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

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

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

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

コメント

タイトルとURLをコピーしました