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

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

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

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

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

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

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

シノ
シノ

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

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

スポンサーリンク

分布数え上げソート

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具体例で見ていこう。

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

i0123456
data[i]7142782
ソートするデータ

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

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

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

i012345678910
box[i]00000000000
箱の中身1

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

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

i012345678910
個数01201002100
累計01334446777
データの分布

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

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

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

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

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

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

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

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

i0123456
data[i]7142782
ソートするデータ

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

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

i012345678910
box[i]01334446777
箱の中身2

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

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

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

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

i0123456
sort[i]??2????
ソート後の配列1

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

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

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

i012345678910
box[i]01234446777
箱の中身3

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

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

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

i0123456
sort[i]??2???8
ソート後の配列2
i012345678910
box[i]01234446677
箱の中身4

このようになる。

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

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

次は7

i0123456
sort[i]??2??78
ソート後の配列3
i012345678910
box[i]01234445677
箱の中身5

次は2

i0123456
sort[i]?22??78
ソート後の配列4
i012345678910
box[i]01134445677
箱の中身6

次は4。

i0123456
sort[i]?224?78
ソート後の配列5
i012345678910
box[i]01133445677
箱の中身7

そして1。

i0123456
sort[i]1224?78
ソート後の配列6
i012345678910
box[i]00133445677
箱の中身8

最後に7だ。

i0123456
sort[i]1224778
ソート後の配列7
i012345678910
box[i]00133444677
箱の中身9

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

色を見ると、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の値を減らすようにしている。

おわりに

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

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

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

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

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

コメント

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