JavaScriptで基数ソート（ラディックスソート）を実装する方法

基数ソート（ラディックスソート）は、整数を「桁」の値に基づいてバケットへ振り分けることで整列を行うアルゴリズムです。クイックソートやマージソートのような比較ベースのソートとは異なり、数値同士を直接比較するのではなく、一の位・十の位・百の位といった桁ごとに段階的に並べ替えていく点が大きな特徴です。

ここでいう「基数」とは、対象となる値がどの記数法に基づいているかを表すものです。一般的な10進数の場合、基数は10となり、各ステップでは0〜9までの10個のバケットが用意されます。

基数ソートの基本的な流れ

1. 配列の中から最大値を求め、必要な桁数を把握します。
2. 下位の桁（一の位）から順に、各数値をその桁の値に応じたバケットへ振り分けます。
3. すべてのバケットを順番に連結し、配列を再構築します。
4. 次の桁（十の位、百の位…）に移り、最大値の桁数に達するまで同じ処理を繰り返します。

JavaScriptでの実装例

以下のコードでは、除数（divisor）を利用して各桁の値を取り出し、バケットへの振り分けと配列の再構築を桁が上がるごとに繰り返しています。

function radixSort(arr) {
    // 最大値を求め、10倍することで最大値より1桁大きい数値を取得
    const maxNum = Math.max(...arr) * 10;
    let divisor = 10;
    while (divisor < maxNum) {
        // 0〜9に対応するバケット配列を作成
        let buckets = [...Array(10)].map(() => []);
        // 各数値の現在注目している桁の値を取得し、対応するバケットへ格納
        for (let num of arr) {
            buckets[Math.floor((num % divisor) / (divisor / 10))].push(num);
        }
        // サブ配列をすべて連結して配列を再構築
        arr = [].concat.apply([], buckets);
        // 次の桁へ移動
        divisor *= 10;
    }
    return arr;
}
console.log(radixSort([5,3,88,235,65,23,4632,234]))

実行結果

[ 3, 5, 23, 65, 88, 234, 235, 4632 ]

このように、一の位から順に「振り分け→連結」を繰り返していくことで、最終的に昇順に整列された配列が得られます。

計算量と特徴

• 時間計算量：O(n × k)（nは要素数、kは最大値の桁数）
• 安定ソート：同じ値を持つ要素の相対的な順序が保たれます
• 比較不要：要素間の大小比較を行わないため、条件がそろえば高速に動作します

負の数や浮動小数点数を扱う場合には別途工夫が必要ですが、非負の整数のソートにおいて基数ソートは非常に効率的な選択肢となります。