前回は、要素同士を比較しないソートとして、ビンソートを解説した。
このようなソートは他にも種類がある。
引き続き、解説をしていこう。
今回は、分布数え上げソートというものを紹介する。
前回のビンソートとの条件の違いなどに気を付けて、使い分けて欲しい。
こちらも、ビンソートと同じくかなり高速!
ただ、条件には気を付けて!
分布数え上げソート
もう名前から想像はつくかもしれない。
分布数え上げソートとは、その名の通りデータの分布を見て、ソートをしていこうという考え方だ。
先に、このソートができる条件を提示しておこう。
- 要素が整数(自然数)
- 要素の範囲が(ある程度)分かっている
(データの下限、上限が決められる)
…前回のビンソートも下限、上限を決められるというのが正確なところか。
というわけで、ビンソートから重複がOKになったような条件となっている。
では、考え方を解説していこう。
まず、ビンソートと同じようにデータが取り得る値と対応する箱を用意する。
ただし、前回はYESorNOの二択だったのに対し、今度は数が入る。
最初は全部0としておこう。
次に、データを順番に見て、そこまでの累計で数が何個出てきているかを箱の中に入れる。
この段階が終わると、データがどのような分布をしているかが分かるようになるのだ。
最後に、この分布を見ればデータが入るところが分かるので、それによってデータを移動させる、という形になる。
なお、このソートはちょっと工夫をすると安定になる。
具体例で見ていこう。
まず、ソートするデータは以下の通り。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
data[i] | 7 | 1 | 4 | 2 | 7 | 8 | 2 |
範囲は、0から10までと分かっているとしよう。
では、箱を用意していく。
最初は全て0にしておくので、以下のような感じだ。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
では、分布を見ていこう。
ちょっと言葉での説明が難しいので、先に以下の表を見て欲しい。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
個数 | 0 | 1 | 2 | 0 | 1 | 0 | 0 | 2 | 1 | 0 | 0 |
累計 | 0 | 1 | 3 | 3 | 4 | 4 | 4 | 6 | 7 | 7 | 7 |
まず、個数という行は、そのi
のデータが、いくつソートする配列に含まれているかを表している。
そして、累計とは、0から見ていったときの、そこまでのデータ数の合計を表している。
最終的にbox
配列に入るのは、この累計の方のデータだ。
私も最初ちょっと勘違いをしていたので、気を付けて欲しい。
最後に、ソートの部分だ。
ここで、ちょっと工夫が入る。
データの、最後の数から順番に見ていこう。
データは、元々以下のような配列になっていた。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
data[i] | 7 | 1 | 4 | 2 | 7 | 8 | 2 |
分かりやすいように、重複しているデータは一つ目を赤、二つ目を青にしてある。
ちょっと離れてしまったので、boxの中身も再掲しておく。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 1 | 3 | 3 | 4 | 4 | 4 | 6 | 7 | 7 | 7 |
では、後ろの2から見ていこう。
box[2]
を見ると、3が入っている。
つまり、2の最後が三つ目に来るということが分かる。
そこで、配列は0から数えるので、3-1=2番目にこの2を入れる。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | ? | ? | 2 | ? | ? | ? | ? |
また、ここでワンポイント。
数を入れたら、そのboxの中身を1減らしておこう。
つまり、boxは以下のようになる。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 1 | 2 | 3 | 4 | 4 | 4 | 6 | 7 | 7 | 7 |
こうすることで、次に2が来たときに、同じ考え方で操作することができるようになる。
では、dataの次を見ていこう。
今度は8が入っているので…
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | ? | ? | 2 | ? | ? | ? | 8 |
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 1 | 2 | 3 | 4 | 4 | 4 | 6 | 6 | 7 | 7 |
このようになる。
以降、同じように進めていく。
数1個ごとの経過をお見せしておこう。
次は7。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | ? | ? | 2 | ? | ? | 7 | 8 |
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 6 | 7 | 7 |
次は2。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | ? | 2 | 2 | ? | ? | 7 | 8 |
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 1 | 1 | 3 | 4 | 4 | 4 | 5 | 6 | 7 | 7 |
次は4。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | ? | 2 | 2 | 4 | ? | 7 | 8 |
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 1 | 1 | 3 | 3 | 4 | 4 | 5 | 6 | 7 | 7 |
そして1。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | 1 | 2 | 2 | 4 | ? | 7 | 8 |
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 0 | 1 | 3 | 3 | 4 | 4 | 5 | 6 | 7 | 7 |
最後に7だ。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
sort[i] | 1 | 2 | 2 | 4 | 7 | 7 | 8 |
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
box[i] | 0 | 0 | 1 | 3 | 3 | 4 | 4 | 4 | 6 | 7 | 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
の値を減らすようにしている。
おわりに
今回は、分布数え上げソートを扱った。
これまでとまた一風変わったソートなので、慣れないと難しいかもしれない。
しかし、データの動きを見ればなんとなく理解できると思うので、一個ずつ順番に理解していこう。
次回は、もう一つの基数ソートと呼ばれるソートをご紹介する。
その中に、この分布数え上げソートが出てくるので、心配な方はしっかり学習しておこう。
コメント