C言語で学ぶ基数ソート（Radix Sort）の仕組みと実装方法

ソート（整列）アルゴリズムとは、リスト内の要素を特定の順序に並べ替えるためのアルゴリズムのことです。最もよく使われる順序としては、数値の昇順・降順や、辞書式（五十音・アルファベット）順などが挙げられます。

基数ソート（Radix Sort）は、要素同士を比較しない「非比較型」のソートアルゴリズムの一つで、ソートされていないリストに対して特に高い効果を発揮する手法として知られています。

基数ソートでは、同じ位の数字ごとに要素をグループ化することで並べ替えを行います。その基本的な考え方は、最下位桁（LSD：Least Significant Digit）から最上位桁（MSD：Most Significant Digit）へ向かって、一桁ずつ昇順または降順にソートを繰り返すというものです。

実際、大規模な名簿を五十音順（アルファベット順）に整理する場面でも、この手法は何度も活用されています。具体的には、まず各名前の一文字目に注目してリストを分類し、五十音（アルファベットなら26種類）ごとのカテゴリーに整理していきます。

以下の図を使って、基数ソートの動作を確認してみましょう。なお、パス（繰り返し処理）の回数は、対象となる数値の中で最大のものの桁数によって決まります。

上の例では、左端の列が元の入力データを表しています。その右側の列は、より上位の桁位置に対してソートを繰り返すたびに、リストがどのように変化していくかを示したものです。

計算量の分析

基数ソートの計算量は O(m・n) です。ここで m はキーの桁数、n は要素の個数を表します。

しかし、この2つの値を比べてみると、キーの総数と比較してキーそのもののサイズは相対的に小さいことが分かります。たとえば6桁のキーであれば、100万件もの異なるレコードを表現できます。

つまり、キーのサイズは本質的には重要な要素ではなく、このアルゴリズムは実質的に線形時間 O(n) の性能を持つと言えます。

アルゴリズム（擬似コード）

Radix_sort (list, n)
shift = 1
for loop = 1 to keysize do
   for entry = 1 to n do
   bucketnumber = (list[entry].key / shift) mod 10
   append (bucket[bucketnumber], list[entry])
list = combinebuckets()
shift = shift * 10

C言語による実装例

以下は、基数ソートをC言語で実装したサンプルプログラムです。まず配列内の最大値から必要なパス回数（桁数）を求め、バケット（bucket）を使った「分配」と「回収」を下位の桁から順に繰り返すことで、全体を昇順に並べ替えます。

#include<stdio.h>
int get_max (int a[], int n){
    int max = a[0];
    for (int i = 1; i < n; i++)
       if (a[i] > max)
          max = a[i];
    return max;
}
void radix_sort (int a[], int n){
    int bucket[10][10], bucket_cnt[10];
    int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
    lar = get_max (a, n);
    while (lar > 0){
       NOP++;
       lar /= 10;
    }
    for (pass = 0; pass < NOP; pass++){
       for (i = 0; i < 10; i++){
          bucket_cnt[i] = 0;
       }
       for (i = 0; i < n; i++){
          r = (a[i] / divisor) % 10;
          bucket[r][bucket_cnt[r]] = a[i];
          bucket_cnt[r] += 1;
       }
       i = 0;
       for (k = 0; k < 10; k++){
          for (j = 0; j < bucket_cnt[k]; j++){
             a[i] = bucket[k][j];
             i++;
          }
       }
       divisor *= 10;
       printf ("After pass %d : ", pass + 1);
       for (i = 0; i < n; i++)
          printf ("%d ", a[i]);
       printf ("\n");
    }
}
int main (){
    int i, n, a[10];
    printf ("Enter the number of items to be sorted: ");
    scanf ("%d", &n);
    printf ("Enter items: ");
    for (i = 0; i < n; i++){
        scanf ("%d", &a[i]);
    }
    radix_sort (a, n);
    printf ("Sorted items : ");
    for (i = 0; i < n; i++)
        printf ("%d ", a[i]);
    printf ("\n");
    return 0;
}

実行結果

Enter number of items to be sorted 6
Enter items:567 789 121 212 563 562
After pass 1 : 121 212 562 563 567 789
After pass 2 : 212 121 562 563 567 789
After pass 3 : 121 212 562 563 567 789
Sorted items : 121 212 562 563 567 789

この出力から、1パス目で最下位桁（一の位）、2パス目で十の位、3パス目で百の位の順にソートが進んでいき、最終的にすべての要素が正しく昇順に並び替えられていることが確認できます。