<解説> 基数Rの各桁Dについて、安定なソート（通常はバケットソート）を繰り返す。
<実行結果 例> D= 0 110 212 323 335 245 257 128 359 (1の位だけでバケットソート、バケツは0-9。Aに戻す) D= 1 110 212 323 128 335 245 257 359 (10の位でバケットソート。1の位での順番はバケツ内で維持) D= 2 110 128 212 245 257 323 335 359 (100の位で。安定なソートの繰り返しになっていることに注意）
<追加解説>
解答例
#include <stdio.h>
#define N 8
#define R 10
#define D 3 /* 最大桁数 digit 今回のデータは3桁 */
/* int rのn乗 */
int ipow (int radix, int n);
int A[N] = {212, 323, 335, 257, 128, 359, 245, 110};
int B[R][N]; /* バケット R番目のバケットには、最大N個格納可能 */
int P[R]; /* R番のバケットがいくつ使用されているかのカウンタ */
/* 配列array 、要素n個をプリント */
void print_array (int array[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%7d", array[i]);
printf("\n");
}
/* 基数rのn乗 */
int ipow (int r, int n) {
int i, j;
j = 1;
for (i = 1; i <= n; i++)
j = r * j;
return (j);
}
int main (void) {
int i, j, k, l;
int e;
/* 基数 */
for (i = 0; i < D; i++) {
/* 配列Pの初期化 */
for (j = 0; j < R; j++)
P[j] = 0;
/* 10のi乗の桁eを取り出し、バケットソート */
for (j = 0; j < N; j++) {
e = A[j]/ipow(R, i);
e = e%R;
B[e][P[e]] = A[j]; /* バケットeのP[e]番目に格納 */
P[e]++; /* バケットeの格納個数をインクリメント */
}
/* 配列Aに並び替え 安定なソートになっていることに注意 */
k = 0;
for (j = 0; j < R; j++) {
if (P[j] > 0) {
for (l = 0; l < P[j] ; l++) {
A[k] = B[j][l];
k++;
}
}
}
printf("D= %d",i);
print_array(A, N); /* 安定なソートになっていることに注意 */
}
return 0;
}}