パンチカードとグレイ符号
5,3,6,9,10,12,4,2,1,11,7,8 //最初の並び 6,10,12,4,2,8/5,3,9,1,11,7 //1の桁で並べかえ 12,4,8,5,9,1/6,10,2,3,11,7 //2の桁 8,9,1,10,2,3,11/12,4,5,6,7 //4の桁 1,2,3,4,5,6,7,8,9,10,11,12 //8の桁
//http://www1.cts.ne.jp/~clab/hsample/Sort/Sort5.html より // RadixSort.cpp : コンソール アプリケーション用のエントリ ポイントの定義 #include "stdafx.h" #include <stdio.h> #define NUM_DATA 10 //定数 int rad[NUM_DATA]; /* 基数に対応する数を記録する整数(int)配列 */ int y[NUM_DATA]; /* 作業用の整数配列 */ /* n 個のデータを表示する関数 */ /* x[ ]:表示するデータ */ /* n:データの数 */ void ShowData(int x[ ], int n) { int i; for (i = 0; i < n ; i++) printf("%d\t", x[i]);//整数x[i]を表示 printf("\n");//改行 } /* 基数法でソートを行う */ /* x[ ]:ソートするデータ */ /* n:データの数 */ /* r:基数の最大値 4桁の数なら1000*/ void RadixSort(int x[ ], int n, int r) { int i, j, k; int m = 1; // 基数 while (m <= r) { for (i = 0; i < n; i++) //i++ :iを1増す rad[i] = (x[i] / m) % 10; /* 基数を取り出し rad[i] に保存 %は余り演算*/ k = 0; /* 次のデータの位置*/ for (i = 0; i <= 9; i++) /* 基数は 0 から 9 */ for (j = 0; j < n; j++) if (rad[j] == i) //基数の小さいものからy[]にコピー y[k++] = x[j]; //y[k++]は y[k]に保存後、kを増加 for (i = 0; i < n; i++) x[i] = y[i]; /* x[ ] にコピーし直す */ /* 途中経過を表示 */ printf("\nソート中:%d の桁でソート\n",m); ShowData(x, n); m *= 10; /* 基数を取り出す桁を一つ上げる */ } } //ここから実行開始 void main(void) { /* ソートするデータ */ int x[NUM_DATA] = { 5489, 1473, 7853, 1058, 9448, 1118, 7979, 2163, 1856, 3117}; int n = 10; /* ソートするデータ数 */ int r = 1000; /* ソートするデータから取り出す基数(最大1000) */ /* ソート前のデータを表示 */ printf("ソート前:\n"); ShowData(x, n); RadixSort(x, n, r); }実行のようす
ソート前: 5489 1473 7853 1058 9448 1118 7979 2163 1856 3117 ソート中:1 の桁でソート 1473 7853 2163 1856 3117 1058 9448 1118 5489 7979 ソート中:10 の桁でソート 3117 1118 9448 7853 1856 1058 2163 1473 7979 5489 ソート中:100 の桁でソート 1058 3117 1118 2163 9448 1473 5489 7853 1856 7979 ソート中:1000 の桁でソート 1058 1118 1473 1856 2163 3117 5489 7853 7979 9448