整列したいデータの取りうる値がm種類あるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づけることを考えます。この概念をソートに応用したアルゴリズムについて説明します。
安定ソートのアルゴリズムとしては、理論上極めて高速なソートを実現できます。ただしm個のバケツのためのメモリを必要とするため、値のデータ長が短く、分布範囲が小さい集合に向いていると言えます。
以下の配列 array に対するソートを行うとします。
| array | 0 | 1 | 0 | 3 | 2 | 0 | 1 | 2 | 0 | 1 |
|---|
値のデータ範囲が 0, 1, 2, 3 であると分かっているとして、どのような構造の「バケツ」を準備すればいいでしょうか。
以下のように、それぞれの値そのものを格納するバケツを考えます。
| buckets[4] | ||||
|---|---|---|---|---|
| 値0用バケツ | 値1用バケツ | 値2用バケツ | 値3用バケツ |
array の先頭から1つずつ値を読み、値ごとのバケツに格納していきます。配列の先頭から読み込むことによって、それぞれのバケツには、以下のように同じ値が出現順に格納されるので、安定ソートが実現できます（bucketsがヒストグラムとして機能する場合は、それぞれのバケツの中で他のソーティングアルゴリズムを適用します）。
| buckets[4] | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|
| 値0用バケツ | 値1用バケツ | 値2用バケツ | 値3用バケツ | |||||||
昇順ソートの場合、値 0 用バケツから順に取り出すと、ソートが完了します。
| array | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
|---|
この場合、「バケツ」は、線形連結リストで実現できます。データの数が充分少なくかつデータ長が充分短ければ、キューによって「バケツ」を実現することもできます。バケツにarrayのデータすべてをコピーするので、バケツの総容量は、arrayと同じサイズを必要とします。
「バケツ」は、それぞれの値が出現した回数を数えるカウンタとして機能します。このとき、値の範囲は明確であることが理想です。
| int buckets[4] | 0 | 0 | 0 | 0 |
|---|---|---|---|---|
| [0]…値0用バケツ | [1]…値1用バケツ | [2]…値2用バケツ | [3]…値3用バケツ |
array の先頭から1つずつ値を読み、値に応じてバケツの中身をインクリメントします。このとき buckets は、度数分布を示しています。
| int buckets[4] | 4 | 3 | 2 | 1 |
|---|---|---|---|---|
| [0]…値0用バケツ | [1]…値1用バケツ | [2]…値2用バケツ | [3]…値3用バケツ |
次に、整列済みの配列として array_dst を準備しておきます
| array_dst | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|---|
一般的に、値 n の書き込みを開始できる要素番号は、buckets[0]からbuckets[n-1]までの総和
として計算できます。
このとき、arrayには 0 が 4
個あり、昇順ソートの場合、最小値である 0 は [0]
から書き込むことができ、1 は [4]、2 は [7]、3 は [9]
から書き込めることが分かります。
arrayを先頭から読み、読みこんだ値に応じて、array_dst の既定の位置に書き込みます。以下は、先頭の 0, 1, 0 を array_dst に書き込んだ例です。
| array_dst | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 |
さらに 3, 2, 0 を array_dst に書き込みます。
| array_dst | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 2 | 3 |
同様に最後まで array_dst に書き込み、ソートが完了します。
| array_dst | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
この場合、「バケツ」は、数値型（整数型）配列で実現できます。線形連結リストを用いる必要がないので実装が簡単になりますが、バケツのサイズとして、arrayに含まれている値の範囲に従った大きさが必要となり、さらに整列済み配列としてarray と同じサイズのメモリ容量を必要とします。
分布数えソートにおいて、「バケツ」は度数分布を示すという考えを発展させます。
| array | 0 | 1 | 0 | 3 | 2 | 0 | 1 | 2 | 0 | 1 |
|---|
| int buckets[4] | 4 | 3 | 2 | 1 |
|---|---|---|---|---|
| [0]…値0用バケツ | [1]…値1用バケツ | [2]…値2用バケツ | [3]…値3用バケツ |
レコードではなく、単純な数値の並べ替えのような単一キーの場合、buckets の要素番号（に対応した値）と度数を参照することによって、array を整列させることができます。
0を4回書き出す
| array | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 2 | 0 | 1 |
|---|
次に、1を3回書き出す
| array | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 0 | 1 |
|---|
次に、2を2回書き出す
| array | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 1 |
|---|
最後に、3を1回書き出す
| array | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
|---|
array の
度数分布を取った後は、度数分布に基づいた繰り返し処理によって、array
の中身を参照することなく、上書きを行うことで、結果として並べ替えが成立します。
単一キーの値集合を扱うため影響はありませんが、安定ソートとはなりません。それ以前に厳密にはソーティングとは言えないかもしれません。しかしながら、配列の走査は読込みと書出しの2回だけで良く、上書き処理のために整列済み配列を準備する必要もなく、array
以外のメモリ領域は buckets
のみという効率的な処理が可能です。
array の中身が、すべて同じ数である可能性を考慮すると、キューを用いたバケツの総容量は (array に含まれる値の総数) * (array に用いられる値の総数) となります。
分布数えソートにおいて、以下のような配列を考えてみます。
| array | 0 | 1 | 0 | 3 | 8 | 0 | 1 | 2 | 0 | 1 |
|---|
このとき、array のに用いられる値は 0, 1, 2, 3, 8 と断続的であり、度数分布のための配列は以下のようになります。
| int buckets[4] | 4 | 3 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] |
結果的に[4]～[7]は、用いられることのない無駄なバケツになってしまいます。
array の定義域が未知である場合、データ型のすべての値を取る可能性を考慮すると、バケツの総容量は
(データ型において取りうるすべての値) * (arrayに用いられる値の総数) * (buckets に格納すべきデータ長)
と、膨大になります。可変長データに至っては、データ型において取りうるすべての値の想定は不可能です。
この問題は、バケツにヒストグラムの機能を持たせて、基数ソートを適用することによって解決できることがあります。
array に含まれる値が、そのまま buckets の要素番号として適用できる場合、計算の機会は array を一度走査するときだけです。
buckets の要素数を決定するにあたって、array
に含まれる値の最小値、最大値、階級幅は既知であることが必要です。未知であれば、これらを求めるための演算が必要です。
array に含まれる値が、そのまま buckets
の要素番号として適用できない場合、両者の対応関係の演算が必要になります。
2008/07/25: 作成