要素同士を比較しない！？分布数え上げソートを解説！

前回は、要素同士を比較しないソートとして、ビンソートを解説した。

このようなソートは他にも種類がある。

引き続き、解説をしていこう。

今回は、分布数え上げソートというものを紹介する。

前回のビンソートとの条件の違いなどに気を付けて、使い分けて欲しい。

シノ

こちらも、ビンソートと同じくかなり高速！

ただ、条件には気を付けて！

分布数え上げソート

もう名前から想像はつくかもしれない。

分布数え上げソートとは、その名の通りデータの分布を見て、ソートをしていこうという考え方だ。

先に、このソートができる条件を提示しておこう。

• 要素が整数(自然数)
• 要素の範囲が(ある程度)分かっている
  (データの下限、上限が決められる)

…前回のビンソートも下限、上限を決められるというのが正確なところか。

というわけで、ビンソートから重複がOKになったような条件となっている。

では、考え方を解説していこう。

まず、ビンソートと同じようにデータが取り得る値と対応する箱を用意する。

ただし、前回はYESorNOの二択だったのに対し、今度は数が入る。

最初は全部0としておこう。

次に、データを順番に見て、そこまでの累計で数が何個出てきているかを箱の中に入れる。

この段階が終わると、データがどのような分布をしているかが分かるようになるのだ。

最後に、この分布を見ればデータが入るところが分かるので、それによってデータを移動させる、という形になる。

なお、このソートはちょっと工夫をすると安定になる。

具体例で見ていこう。

まず、ソートするデータは以下の通り。

範囲は、0から10までと分かっているとしよう。

では、箱を用意していく。

最初は全て0にしておくので、以下のような感じだ。

では、分布を見ていこう。

ちょっと言葉での説明が難しいので、先に以下の表を見て欲しい。

まず、個数という行は、そのiのデータが、いくつソートする配列に含まれているかを表している。

そして、累計とは、0から見ていったときの、そこまでのデータ数の合計を表している。

最終的にbox配列に入るのは、この累計の方のデータだ。

私も最初ちょっと勘違いをしていたので、気を付けて欲しい。

最後に、ソートの部分だ。

ここで、ちょっと工夫が入る。

データの、最後の数から順番に見ていこう。

データは、元々以下のような配列になっていた。

分かりやすいように、重複しているデータは一つ目を赤、二つ目を青にしてある。

ちょっと離れてしまったので、boxの中身も再掲しておく。

では、後ろの2から見ていこう。

box[2]を見ると、3が入っている。

つまり、2の最後が三つ目に来るということが分かる。

そこで、配列は0から数えるので、3-1=2番目にこの2を入れる。

また、ここでワンポイント。

数を入れたら、そのboxの中身を1減らしておこう。

つまり、boxは以下のようになる。

こうすることで、次に2が来たときに、同じ考え方で操作することができるようになる。

では、dataの次を見ていこう。

今度は8が入っているので…

このようになる。

以降、同じように進めていく。

数1個ごとの経過をお見せしておこう。

次は7。

次は2。

次は4。

そして1。

最後に7だ。

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

色を見ると、2と7どちらも赤→青の順番なので、安定になっていることも分かる。

なお、これまでと異なり、入力を直接入れ替えるものではない。

そのため、結果用の領域も必要なことに注意しよう。

分布数え上げソートの計算量

お次に計算量だ。

分布数え上げソートの計算量は、\(O(n)\)で表すことができる。

基本的な考え方はビンソートとほぼ同じ。

用意する箱の数をmとすると、実際には\(O(m + n)\)となる。

ある程度箱が小さければ、定数倍として無視できるので、最終的に\(O(n)\)で表せるということだ。

ただ、これもビンソートと同じく、箱のサイズがあまりに大きいと、計算量が増えてしまう。

また、条件も健在なので、本当にこれがいいのか、しっかり確認しておこう。

分布数え上げソートのサンプルプログラム

最後に、サンプルプログラムを。

なお、これまでと違い、入力はソートするdata配列とそのデータの最大値data_max。

出力を、ソートがされた配列としよう。

つまり、引数のdata配列がそのままソートされるわけではないので注意。

function DistCountSort(data, data_max){
    let box = [];

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

    for(let i = 0; i < data.length; i++){
        box[data[i]]++;
    }
    for(let i = 0; i < data_max; i++){
        box[i + 1] += box[i];
    }

    let res = [];
    for(let i = data.length - 1; i >= 0; i--){
        box[data[i]]--;
        res[box[data[i]]] = data[i];
    }
    return res;
}

for文ごとに補足を。

一つ目のfor文は、boxの初期化だ。

二つ目は、単純にその数をカウントしている。

三つ目は、累積を求めるためのものだ。

最後が、後ろからデータを入れていくもの。

なお、先にboxの値を減らすようにしている。

おわりに

今回は、分布数え上げソートを扱った。

これまでとまた一風変わったソートなので、慣れないと難しいかもしれない。

しかし、データの動きを見ればなんとなく理解できると思うので、一個ずつ順番に理解していこう。

次回は、もう一つの基数ソートと呼ばれるソートをご紹介する。

その中に、この分布数え上げソートが出てくるので、心配な方はしっかり学習しておこう。