分布数え上げソートは、ソート元の配列の末尾の値から、以下の処理を繰り返す事で、ソートされた配列をえるこがでいます。以下の処理とは、
カウンタテーブルを用意する。
ソート後の配列の入れ物を用意する。
配列に格納された値に対して、カウンタテーブルにソート後のインデックスを問い合わせ、ソート後の配列に値を格納します。
1.カウンタテーブルを用意する。
「カウンタテーブルを用意する」に関しての詳細を説明します。カウンタテーブルは、値に対して、ソート後のIndexを教える仕組みです。カウンタテーブルは、配列で実装します。手順は以下の通りです。
1.1.ソート元の配列の最小値から最大値までが格納可能な配列(カウンタテーブル)を用意する。
最小値MINが配列要素の0の位置になり、最大値MAXが配列要素のMAX - MIN - 1となるような配列を用意します。
今回の例では、最小値が0で最大値が5なので、カウンタテーブルは6つの要素を6個の要素を持つ配列を生成することになります。また、C#では値型の配列の要素の初期値は指定しないと0になるので初期化する必要はありませんが、後の処理のため要素を0にしておく必要があります。
1.2.ソート前の配列の値をカウンタテーブルに数え上げます。
今回の例では、
0は2個あるので、カウンタテーブルの0番目の要素の値は2
1は1個あるので、カウンタテーブルの1番目の要素の値は1
2は0個あるので、カウンタテーブルの2番目の要素の値は0
3は3個あるので、カウンタテーブルの3番目の要素の値は3
4は0個あるので、カウンタテーブルの4番目の要素の値は0
5は2個あるので、カウンタテーブルの5番目の要素の値は2
1.3.カウンタテーブルを累積個数にする。
N番目の要素の値を、0からN番目の値の合計に変換します。累積させることにより、たとえばソート前の3という値は、ソート後の3〜5のインデックスに配置されるということが分かるようになります。
カウンタテーブルの0番目の要素は、0未満の要素がないので、累積個数は2個
カウンタテーブルの1番目の要素は、2 + 1 で、累積個数は3個
カウンタテーブルの2番目の要素は、2 + 1 + 0 で、累積個数は3個
カウンタテーブルの3番目の要素は、2 + 1 + 0 + 3 で、累積個数は6個
カウンタテーブルの4番目の要素は、2 + 1 + 0 + 3 + 0 で、累積個数は6個
カウンタテーブルの5番目の要素は、2 + 1 + 0 + 3 + 0 + 2 で、累積個数は8個
ということで、カウンタテーブルの作成は完了です。
2.ソート後の配列の入れ物を用意する。
2.1.ソート前の配列の末尾からカウンタテーブルに配置先を問い合わせて再配置していきます。
さらに、カウンタテーブルは、問い合わされたインデックスの値をデクリメントします。
末尾から処理を行うのは、安定ソートを実現するためです。先頭からおこなった場合、重複キーが存在した場合、重複キー内で順序が逆順になってしまいます。
ソート元の配列の要素の値が、カウンタテーブルのインデックスに対応し、対応したカウンタテーブルの要素の値がソート後の配列のインデックス、つまり格納先になります。
これで、最終的には以下のようになります。
「分散数え上げソート」のお絵かき終わり!
C#で実装すると下記のようになります。
public static int[] Sort(int[] arrary)
{
int max = arrary.Max();
int min = arrary.Min();
// 配列のインデックスがarraryの個々の値 - minに対応する配列を用意する。
// 言語仕様により配列の要素が0になっていることを期待している。
// ex) arraryが{-1,4,4,5}の場合は、{0,0,0,0,0,0,0}という配列を用意される。
var countTable = new int[max - min + 1];
// arraryの要素の値をcountTableの添え字と見立てて、countTableにarraryの値の分布を作成
// ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}という配列になる。
foreach (int value in arrary)
{
countTable[value - min]++;
}
// 分布を累積分布に変換する。
// ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}から{1,1,1,1,1,3,4}という配列になる。
for (int i = 0; i < countTable.Length - 1; i++)
{
countTable[i + 1] += countTable[i];
}
var result = new int[arrary.Length];
for (int arraryIndex = arrary.Length - 1; arraryIndex >= 0; arraryIndex--)
{
// arrayの要素の値からcountTableを参考に、結果の配列の格納先の添え字を決定する。
// 使用したcountTableの要素の値を、使用した目印をつけるため1デクリメントする。
int countTableIndex = arrary[arraryIndex] - min;
countTable[countTableIndex] -= 1;
int resultIndex = countTable[countTableIndex];
result[resultIndex] = arrary[arraryIndex];
}
return result;
}