どちらも範囲の決まった整数をソートするときにO(n)でソートできるという優れものです。アルゴリズムがどうだったか忘れてしまったので改めて調べることに。例として
- 最大値 = 30
- 最小値 = 20
- データ数 = 5
の場合を考えたいと思います。
分布数えソート
これは簡単。データの範囲で分布を数え、その数にしたがってソート済みの配列を復元します。分布を格納するため、データの範囲と同じ大きさの配列(dist)が使われます。
data[000]=21 dist[000(20)]=0 sort[000]=21
data[001]=26 dist[001(21)]=2 sort[001]=21
data[002]=27 dist[002(22)]=0 sort[002]=26
data[003]=21 dist[003(23)]=0 sort[003]=27
data[004]=29 dist[004(24)]=0 sort[004]=29
dist[005(25)]=0
dist[006(26)]=1
dist[007(27)]=1
dist[008(28)]=0
dist[009(29)]=1このカウントを使ってそのまま復元すればいいのですが、プログラムが簡単になるからか、以下のような累積分布にしてから復元するものが多いようです。
data[000]=21 dist[000(20)]=0 sort[000]=21
data[001]=26 dist[001(21)]=2 sort[001]=21
data[002]=27 dist[002(22)]=2 sort[002]=26
data[003]=21 dist[003(23)]=2 sort[003]=27
data[004]=29 dist[004(24)]=2 sort[004]=29
dist[005(25)]=2
dist[006(26)]=3
dist[007(27)]=4
dist[008(28)]=4
dist[009(29)]=5手順としては
- data[0]=21を取得
- dist[1(21)]=2なので、dist[1]の値を1減らして(2-1=1)ソート済み配列へのインデックスを求める
- (1〜2も同様)
- data[3]=21を取得
- dist[1(21)]=1なので、dist[1]の値を1減らして(1-1=0)ソート済み配列へのインデックスを求める
という感じ。累積分布自体を配列のインデックスにするという発想ですね。
逆写像ソート
逆写像ソートとは、各データ要素ごとに、対応する元データのインデックスを辿ることによりソートを行う手法です。インデックス格納用の配列(index)と、作業用配列(work)が必要になります。
言葉で言うと分かりにくいので、下に実際のソート過程を出してみました。
data[000]=28 index[000(20)]=1 work[000]=2 sort[000]=20
data[001]=20 index[001(21)]=-1 work[001]=-1 sort[001]=23
data[002]=28 index[002(22)]=-1 work[002]=-1 sort[002]=23
data[003]=23 index[003(23)]=3 work[003]=4 sort[003]=28
data[004]=23 index[004(24)]=-1 work[004]=-1 sort[004]=28
index[005(25)]=-1
index[006(26)]=-1
index[007(27)]=-1
index[008(28)]=0
index[009(29)]=-1indexは、それぞれの数字が最初に入っている元データへのインデックスです。データの復元順序としては
- index[0]=1を取得
- data[1]=20を復元
- 次のインデックスがwork[1]に入っている
- -1なので終了
- index[1]=index[2]=-1なので飛ばす
- index[3]=3を取得
- data[3]=23を復元
- 次のインデックスがwork[3]に入っている
- data[4]=23を復元
- 続く。
という感じで、まず最初のインデックスをindexからとってきて、あとはworkからインデックスを辿るという流れになります。・・・ってやっぱり分かりにくいな。図を描けばもっと分かりやすいのですが。
ソース
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 30
#define MIN 20
#define NUM 5
void initdata(int []);
void mapsort(int [], int []);
void distsort1(int [], int []);
void distsort2(int [], int []);
void printdata(int [], int, char *);
int main(void){
int data[NUM], sort[NUM];
srand((unsigned int)time(NULL));
initdata(data);
mapsort(data, sort);
return 0;
}
void mapsort(int data[], int sort[])
{
int i, j, a;
int index[MAX-MIN], work[NUM];
for(i=0; i<MAX-MIN; i++){
index[i] = -1;
}
for(i=NUM-1; i>=0; i--){
a = data[i] - MIN;
work[i] = index[a];
index[a] = i;
}
for(i=0, j=0; i<MAX-MIN; i++){
a = index[i];
while(a >= 0){
sort[j++] = data[a];
a = work[a];
}
}
printdata(data, NUM, "data");
printdata(work, NUM, "work");
printdata(index, MAX-MIN, "index");
printdata(sort, NUM, "sort");
}
void distsort1(int data[], int sort[])
{
int i;
int dist[MAX-MIN];
for(i=0; i<MAX-MIN; i++){
dist[i] = 0;
}
for(i=0; i<NUM; i++){
dist[data[i]-MIN]++;
}
for(i=1; i<MAX-MIN; i++){
dist[i] += dist[i-1];
}
for(i=0; i<NUM; i++){
sort[--dist[data[i]-MIN]] = data[i];
}
printdata(data, NUM, "data");
printdata(dist, MAX-MIN, "dist");
printdata(sort, NUM, "sort");
}
void distsort2(int data[], int sort[])
{
int i, j, k;
int dist[MAX-MIN];
for(i=0; i<MAX-MIN; i++){
dist[i] = 0;
}
for(i=0; i<NUM; i++){
dist[data[i]-MIN]++;
}
for(i=0, k=0; i<MAX-MIN; i++){
for(j=0; j<dist[i]; j++){
sort[k++] = i + MIN;
}
}
printdata(data, NUM, "data");
printdata(dist, MAX-MIN, "dist");
printdata(sort, NUM, "sort");
}
void initdata(int data[]){
int i;
for(i=0; i<NUM; i++){
data[i] = MIN + ((double)(MAX-MIN) * rand()/(RAND_MAX + 1.0));
}
}
void printdata(int data[], int n, char *s){
int i;
for(i=0; i<n; i++){
printf("%s[%03d]=%d\n", s, i, data[i]);
}
}
