基数ソート（Radix Sort）とは？仕組み・計算量・C++実装例をわかりやすく解説

基数ソートとは

基数ソート（Radix Sort）は、非比較型のソートアルゴリズムの一つです。クイックソートやマージソートのように要素同士を比較して大小関係を判定するのではなく、整数キーを構成する各桁に着目し、同じ位（けた）・同じ値を持つ数字同士をグループ化することで整列を行います。

「基数（radix）」とは記数法における底（base）のことです。私たちが日常的に使う10進法では基数が10であるため、10進数のデータをソートする際には、0〜9までの10個のポケット（バケット）を用意して数値を振り分けることになります。

基数ソートの計算量

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

入力と出力の例

入力：
ソート前のリスト：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

アルゴリズム

基数ソートの処理手順を、以下の擬似コードで表します。

radixSort(array, size, maxDigit)

入力 − ソート対象のデータ配列、配列内の要素総数、最大値の桁数

出力 − ソート済みの配列

Begin
    define 10 lists as pocket
    for i := 0 to max -1 do
        m = 10^i+1
        p := 10^i
        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] is not empty
                array[count] := get first node of pocket[j] and delete it
                count := count +1
        done
    done
End

C++による実装例

続いて、実際のC++コードを紹介します。このプログラムでは、std::list を10個用意し、各桁の値に応じて要素を振り分けた後、先頭から取り出して配列に戻す処理を最大桁数回繰り返しています。

#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]; //radix of decimal number is 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;  //find index for pocket array
            pocket[index].push_back(arr[j]);
        }

        count = 0;
        for(j = 0; j<10; j++) {
            //delete from linked lists and store to array
            while(!pocket[j].empty()) {
                arr[count] = *(pocket[j].begin());
                pocket[j].erase(pocket[j].begin());
                count++;
            }
        }
    }
}

int main() {
    int n, max;
    cout << "Enter the number of elements: ";
    cin >> n;
    cout << "Enter the maximum digit of elements: ";
    cin >> max;
    int arr[n]; //create an array with given number of elements
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Data before Sorting: ";
    display(arr, n);
    radixSort(arr, n, max);
    cout << "Data after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter the maximum digit of elements: 3
Enter elements:
802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932

このように、基数ソートは各桁ごとの分類を繰り返すだけで安定した整列を実現できます。要素間の比較を行わないため、桁数が限られた大量の整数データを高速に並べ替えたい場合に特に有効な手法といえます。