基数ソート¶

前節では計数ソートを紹介しました。これは、データ量 \(n\) が大きく、データ範囲 \(m\) が小さい場合に適しています。\(n = 10^6\) 個の学籍番号をソートすると仮定すると、学籍番号は \(8\) 桁の数字なので、データ範囲 \(m = 10^8\) は非常に大きくなります。計数ソートでは大量のメモリ空間を確保する必要がありますが、基数ソートではこの問題を回避できます。

基数ソート（radix sort）の基本的な考え方は計数ソートと同じで、個数を数えることによってソートを実現します。そのうえで、基数ソートは各桁の段階的な関係を利用し、各桁を順にソートすることで、最終的なソート結果を得ます。

アルゴリズムの流れ¶

学籍番号データを例にすると、数字の最下位桁を第 \(1\) 位、最上位桁を第 \(8\) 位としたとき、基数ソートの流れは次図のようになります。

桁番号 \(k = 1\) を初期化します。
学籍番号の第 \(k\) 位に対して「計数ソート」を実行します。完了すると、データは第 \(k\) 位に従って昇順に並びます。
\(k\) を \(1\) 増やし、手順 2. に戻って反復を続けます。すべての桁のソートが完了したら終了します。

以下ではコード実装を分解して見ていきます。\(d\) 進数の数値 \(x\) について、その第 \(k\) 位 \(x_k\) を取得するには、次の計算式を用います。

\[ x_k = \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d \]

ここで、\(\lfloor a \rfloor\) は浮動小数点数 \(a\) の切り捨てを表し、\(\bmod \: d\) は \(d\) による剰余を表します。学籍番号データでは、\(d = 10\) かつ \(k \in [1, 8]\) です。

さらに、数字の第 \(k\) 位に基づいてソートできるように、計数ソートのコードを少し変更する必要があります。

[file]{radix_sort}-[class]{}-[func]{radix_sort}

なぜ最下位桁からソートするのですか？

連続するソートの各ラウンドでは、後のラウンドの結果が前のラウンドの結果を上書きします。たとえば、第1ラウンドで \(a < b\) となっていても、第2ラウンドで \(a > b\) となれば、第2ラウンドの結果が優先されます。数字では高位の優先度が低位より高いため、先に低位をソートし、その後で高位をソートする必要があります。

アルゴリズムの特徴¶

計数ソートと比べると、基数ソートは値の範囲が大きい場合に適しています。ただし、データが固定桁数の形式で表せること、かつ桁数が大きすぎないことが前提です。たとえば、浮動小数点数は基数ソートに適していません。桁数 \(k\) が大きすぎて、時間計算量が \(O(nk) \gg O(n^2)\) になる可能性があるためです。

時間計算量は \(O(nk)\)、非適応ソート：データ量を \(n\)、データが \(d\) 進数、最大桁数を \(k\) とすると、ある1桁に対して計数ソートを実行する時間は \(O(n + d)\) であり、全 \(k\) 桁をソートする時間は \(O((n + d)k)\) です。通常、\(d\) と \(k\) はどちらも比較的小さいため、時間計算量は \(O(n)\) に近づきます。
空間計算量は \(O(n + d)\)、非原地ソート：計数ソートと同様に、基数ソートでは長さ \(n\) と \(d\) の配列 res と counter を補助的に用います。
安定ソート：計数ソートが安定であれば基数ソートも安定です。計数ソートが不安定な場合、基数ソートでは正しいソート結果を保証できません。