サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ソート＞基数ソート
/* 今日は基数 ( Radix ) ソートについて、学びます。基数ソートでは、まず、１の位の数を見て、ソートします。結果はこのようになります。
ソート前：12, 34, 91, 16, 83
ソート後：91, 12, 83, 34, 16
上のソートの結果では、12 と 16 の振る舞いに注目して下さい。最初のソートで、当然ですが、12 の方が先頭に近くなっています。この関係が保たれたまま、２桁目の値でソートを行います。下記の結果が得られます。
結果：12, 16, 34, 83, 91
ある桁をソートする時、その桁の数が同じものは、その前のソートの結果が保存されたままソートされます。この、前後関係が保たれたまま、次のソートが行われる点が、基数ソートの原理です。
次々回に扱うビンソートでは、ソートする配列の要素が少なく、取りうる値の範囲が広いと、メモリ効率が悪くなるという欠点があります。基数ソートでは、この点は問題になりません。しかし、整数しか扱えないという制約は、依然として存在します。
基数ソートのアルゴリズムは、古くから知られています。
RadixSort( ) は、三つの引数を取ります。
int x[ ]：ソート対象の配列
int n： 配列要素の数
int r： 基数を取り出す最大値
静的領域には、次の配列を宣言しておきます。
rad[ ]：基数をしまう配列
y[ ]： 作業用配列
x[ ] と rad[ ] と y[ ] のサイズは同じでなければなりません。
i の値を for ループの中で、０から n まで変化させて、下記の計算を行います。
(x[i] / m) % 10
m の初期値は１なので、この計算をすると、x[i] の１の位の基数が求まります。これを配列 rad[i] に保存します。rad[ ] は x[ ] の基数の配列になります。
次の for ループの中で、rad[ ] の値の小さいものから順に取り出し、その添字と等しい x[ ] の要素を、y[ ] にコピーします。この時にソートが行われます。次いで、配列 y[ ] の値を配列 x[ ] にコピーし直します。
一連の操作を終わった所で、 m の値を１０倍します。整数どおしの計算では、余りは切り捨てられます。 そこで、次の計算で、１０の位の数を取り出すことができます。
(x[i] / m) % 10
以上の手順を m が r を越えない間繰り返せば、ソートが完成します。
以上のアルゴリズムをコードにしたのが、今回のソースプログラムです。
基数ソートはビンソートやバブルソートと同様に、データのばらつきかたの影響を受けません。 */
#include <stdio.h> void RadixSort(int x[ ], int n, int r); void ShowData(int x[ ], int n); void main(void); #define NUM_DATA 10 static int rad[NUM_DATA]; /* 基数をしまう配列 */ static int y[NUM_DATA]; /* 作業用配列 */ /* 基数ソートを行う */ void RadixSort(int x[ ], int n, int r) /* x[ ]：ソートするデータ */ { /* n：データの数 */ int i, j, k; /* r：基数を取り出す最大値 */ int m = 1; /* 基数を取り出す桁 */ while (m <= r) { for (i = 0; i < n; i++) 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[k++] = x[j]; /* y[ ] にコピー */ for (i = 0; i < n; i++) x[i] = y[i]; /* x[ ] にコピーし直す */ /* 途中経過を表示 */ printf("\nソート中:\n"); ShowData(x, n); m *= 10; /* 基数を取り出す桁を一つ上げる */ } } /* n 個のデータを表示する */ void ShowData(int x[ ], int n) { int i; for (i = 0; i < n ; i++) printf("%d\t", x[i]); } void main(void) { /* ソートするデータ */ int x[NUM_DATA] = { 5489, 1473, 7853, 1058, 9448, 1118, 7979, 2163, 1856, 3117 }; int n = 10; /* ソートするデータ数 */ int r = 1000; /* ソートするデータから取り出す基数の上限 */ /* ソート前のデータを表示 */ printf("ソート前:\n"); ShowData(x, n); printf("\n"); RadixSort(x, n, r); /* ソート後のデータを表示 */ printf("\n\nソート後:\n"); ShowData(x, n); } |
/* プログラムを実行すると、ソートの途中経過も表示されます。基数ソートの進行の様子を確認して下さい。 */
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−