STEP 9.2　バケットソート (p. 65)

<解説>　

<問題> データの個数N=8　(値の可能性は、1-30)　のとき、バケットソートを作成せよ。
データは A[N] = {6, 9, 6, 7, 2, 23, 10, 4}; とする。

<実行結果 例>　（プログラム中で、ソート前データを宣言しています）
  6  9  6  7  2 23 10  4
B[ 2][ 0] =   2　（格納終了後、順番に値をプリントする。ソート済となる)
B[ 4][ 0] =   4
B[ 6][ 0] =   6
B[ 6][ 1] =   6
B[ 7][ 0] =   7
B[ 9][ 0] =   9
B[10][ 0] =  10
B[23][ 0] =  23
解答例

#include <stdio.h>

#define N 8   /* データの個数 */
#define M 30  /* データ値は 1 - 30 */

int A[N] = {6, 9, 6, 7, 2, 23, 10, 4};
int B[M+1][N];
int P[M+1];

/* 配列プリント */
void print_array (int array[], int n);

void print_array (int array[], int n) {
   int i;
   for (i = 0; i < n; i++)
      printf("%3d", array[i]);
   printf("\n");
}


int main (void) {
   int i,j;

   print_array(A, N);

   /* バケットの準備 バケット内個数をすべてを0に初期化 バケット配列そのものは初期化していない */
   for (i = 1; i <= M; i++)
      P[i] = 0;

   /* バケットB[i]に格納。バケットiの格納個数P[i]をインクリメント */
   /* データの個数Nに比例して、処理の時間が増加する。 O(n) 限定された状況で、最高速 */
   /* 教科書は、キューを用いているので、pp.66-67に計算量の議論がある */
   for (i = 0; i < N; i++) {
      B[A[i]][P[A[i]]] = A[i];
      P[A[i]]++;
   }

   /* 表示 ここはオプションなので、O記法の対象外 */
   for (i = 1; i <= M; i++) {
      if (P[i] > 0)
         for (j = 0; j < P[i]; j++)
            printf("B[%2d][%2d] = %3d \n",i, j, B[i][j]);
   }
}