C++で基数ソート（ラディックスソート）を実装するプログラム

基数ソート（ラディックスソート）は、非比較型のソートアルゴリズムの一つです。要素同士を直接比較するのではなく、整数キーを構成する各桁に注目し、同じ桁位置・同じ値を持つ数字どうしをグループ化しながら並べ替えを行います。

「基数」とは記数法における底のことです。私たちが普段使う10進法では基数は10であるため、10進数を基数ソートで並べ替える際には、数値を一時的に格納するための10個のバケット（ポケット）が必要になります。

基数ソートの計算量

• 時間計算量： O(nk)　※nは要素数、kは最大桁数

• 空間計算量： O(n+k)

入力 − ソート前のデータ： 802 630 20 745 52 300 612 932 78 187
出力 − ソート後のデータ： 20 52 78 187 300 612 630 745 802 932

アルゴリズム

radixSort(array, size, maxDigit)

入力: データの配列、配列内の要素の総数、最大値の桁数。

出力: ソート済みの配列。

Begin
    10個のリストを pocket として定義する
    for i := 0 to max -1 do
        m = 10<sup>i+1</sup>
        p := 10<sup>i</sup>
        for j := 0 to n-1 do
            temp := array[j] mod m
            index := temp / p
            pocket[index].append(array[j])
        done
    count := 0
    for j := 0 to radix do
        while pocket[j] が空でない間
            array[count] := pocket[j] の先頭ノードを取り出して削除
            count := count +1
        done
    done
End

このアルゴリズムでは、まず最下位の桁（1の位）から順に着目し、その桁の値に応じて各要素を対応するバケットへ振り分けます。その後、バケット0から9の順に要素を元の配列へ戻す操作を、上位の桁について繰り返します。この処理を最大桁数ぶん行うことで、配列全体が昇順に整列されます。

サンプルコード

#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}
void radixSort(int *arr, int n, int max) {
    int i, j, m, p = 1, index, temp, count = 0;
    list<int> pocket[10];      // 10進数の基数は10
    for(i = 0; i< max; i++) {
        m = pow(10, i+1);
        p = pow(10, i);
        for(j = 0; j<n; j++) {
            temp = arr[j]%m;
            index = temp/p;      // バケット配列のインデックスを求める
            pocket[index].push_back(arr[j]);
        }
        count = 0;
        for(j = 0; j<10; j++) {
            // リンクリストから削除しながら配列へ格納し直す
            while(!pocket[j].empty()) {
                arr[count] = *(pocket[j].begin());
                pocket[j].erase(pocket[j].begin());
                count++;
            }
        }
    }
}
int main() {
   int n, max;
   cout << "要素数を入力してください： ";
   cin >> n;
   cout << "要素の最大桁数を入力してください： ";
   cin >> max;
   int arr[n]; // 指定された要素数で配列を作成
   cout << "要素を入力してください：" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "ソート前のデータ： ";
   display(arr, n);
   radixSort(arr, n, max);
   cout << "ソート後のデータ： ";
   display(arr, n);
}

実行結果

要素数を入力してください： 10
要素の最大桁数を入力してください： 3
要素を入力してください：
802 630 20 745 52 300 612 932 78 187
ソート前のデータ： 802 630 20 745 52 300 612 932 78 187
ソート後のデータ： 20 52 78 187 300 612 630 745 802 932

このように、基数ソートはクイックソートやマージソートのような比較ベースのソートとは異なり、桁ごとの振り分けだけで整列を行える点が大きな特徴です。特に、桁数kが小さく要素数nが多い整数データに対しては、O(nk)という効率的な性能を発揮します。