基数ソートとは

基数ソートとは、バケットソートの欠点でもある、「ソート対象のデータ(キー)の取りうる値が m種類 であること」という前提を解消した、改良版バケットソートのともいえるアルゴリズムです。基数とは、位取りの基準となる数(10進数であれば0～9)を指します。基数ソートはこの基数をキーとして、桁数分のバケットソートを行います。

基数ソートでもバケットソートと同様に、「ソート対象のデータ(キー)の取りうる値の桁数が k であること」という制限が必要です。ただし桁数という意味ではたかが知れており、32bit整数値の場合で10桁程度です。これはバケットソートだと43億個のバケツを用意しなければならない点を考慮すると限りなく少なく済んでいることがわかります。

3桁の整数を対象に基数ソートを実行する場合、まずは1桁めの数でバケットソートを行います。続けて、2桁目3桁目でもバケットソートを行うと、最終的にはソート済のデータが取得できます。これはバケットソートが安定ソートとして実装できる点を活かしています。例えば、{ 151, 129 } を1桁目をキーにソートすると { 151, 129 } 続けて2桁目でソートすると { 129, 151 } となります。3桁目でのソートでは同じキー(1)ですが、バケットソート自体が安定ソートの為、2桁目までの大小関係が保持されたままソートが完了します。

基数ソートは、安定 な 外部 ソートです。k回のバケットソートを実行するので、計算量は O(nk) となります。

基数ソートのシミュレーション

シミュレータでは最大3桁の整数値(0～999)をソートします。動き自体はバケットソートと変わらないのですが、1桁目の値から順に3度バケットソートが実行されているのがわかります。

アルゴリズムの解説

10進数版(0～999)

最大3桁の整数値(0～999)についてのデータを基数ソートでソートする場合を考えます。

  1. 基数の取りうる値(k=10)の数だけバケツを用意します。
  2. ソート対象データについて１桁目をキーにバケットソートを実行します。
  3. ２桁目、３桁目についても同様にバケットソートを実行します。

ビット列版(応用)

通常コンピュータの内部データは10進数ではなく、4バイトや8バイトのビット列です。したがって、10進数の乗除算よりも、ビット演算を使用する方が処理コストが低く済みます。上記の10進数の基数ソートでは、k桁目を求める際に商と余りを求める計算を行う必要がありますが、これをビット演算に置き換えてみます。

32bit整数値は4バイトなので、1バイト毎にバケットソートを適用すれば4回のソートで済むうえ、ビット演算を使うことで高速な処理が期待できます。例えば2バイト目を取り出すには、8ビット分右シフトして255(1バイト)でマスク演算します。すると2バイトの値が計算できます。具体的にはサンプルコードを参照してください。

サンプルコード

C#

// 整数値(10進数最大m桁)の配列をソート
public static void RadixSort10(int[] array, int m)
{
    // バケットの用意
    var buckets = new List<int>[10];

    // m桁分バケットソートを繰り返す
    for (int d = 1, r = 1; d <= m; d++, r *= 10)
    {
        // 配列の中身をバケツに値を入れる
        for (int i = 0; i < array.Length; i++)
        {
            // d桁目の値を取り出す
            int key = (array[i] / r) % 10;
            // バケットに入れる
            if (buckets[key] == null) buckets[key] = new List<int>();
            buckets[key].Add(array[i]);
        }
        // バケット内の値を配列に戻す
        int a = 0;
        for (int i = 0; i < buckets.Length; i++)
        {
            if (buckets[i] != null)
            {
                for (int j = 0; j < buckets[i].Count; j++)
                {
                    array[a++] = buckets[i][j];
                }
            }
        }
        // バケットの中身を空にしておく
        for (int i = 0; i < buckets.Length; i++)　buckets[i].Clear();
    }
}

// 整数値(4バイト)をキー(1バイト)とする任意の型に対する基数ソート
public static void RadixSort<T>(T[] array, Func<T, int> getKey)
{
    // 1バイト取り出すマスク用の数値
    const int mask = 255;

    // 1バイト(2^8) = 256桁分のバケットを用意
    var buckets = new List<T>[256];
    for (int i = 0; i < 256; i++) buckets[i] = new List<T>();

    // 4バイト分ループしてバケットソート
    for (int d = 0; d < 4; d++)
    {
        // バケットに値を入れていく
        for (int i = 0; i < array.Length; i++)
        {
            // 右シフトで d+1 バイト目の値を1バイト目に移動
            // 1バイト(255)でマスクすることで値を取得
            int key = (getKey(array[i]) >> d * 8) & mask;
            buckets[key].Add(array[i]);
        }
        // バケットの中身を結合する
        int a = 0;
        for (int i = 0; i < buckets.Length; i++)
        {
            for (int j = 0; j < buckets[i].Count; j++)
            {
                array[a++] = buckets[i][j];
            }
        }
        // バケットの中身を空にする
        for (int i = 0; i < buckets.Length; i++)　buckets[i].Clear();
    }
}

Python

# 基数ソート(10進整数最大m桁)
def radix_sort(array, m):
    bucket = list()
    for i in range(10):
        bucket.append(list())

    # m桁分バケットソート
    for d in range(1, m+1, 1):
        r = 10**(d-1)

        for val in array:
            # d桁目の値を取り出す
            key = int(val / r) % 10

            # バケットに追加(カウント)
            bucket[key].append(val)

        # バケツの中身を取り出して結合
        i = 0
        for values in bucket:
            for val in values:
                array[i] = val
                i += 1

        # バケットの中身を初期化
        for j in range(len(bucket)):
            bucket[j] = list()