JavaScriptで基数ソート（Radix Sort）を実装する方法

基数ソート（Radix Sort）とは？

基数ソート（ラディックスソート）は、整数のキーを持つデータを、同じ桁位置・同じ値を持つ「桁」ごとにグループ分けしながら並べ替えていくソートアルゴリズムです。比較ベースのクイックソートやマージソートとは異なり、桁の値を直接利用してバケット（桶）に振り分けることで、整列を行います。

計算量は、要素数を n、最大桁数を d、基数を b とすると O(d × (n + b)) となり、条件が揃えば非常に高速に動作するのが特徴です。

実装の要件

ここでは、リテラルの配列を唯一の引数として受け取る JavaScript 関数を作成します。この関数は、基数ソートのアルゴリズムを使って、配列を昇順（または降順）に並べ替えた結果を返します。

アルゴリズムの流れ

1. 1の位から順に、各要素をその桁の値に対応するバケット（0〜9 の10個）へ振り分けます。
2. バケットの順番通りに要素を取り出し、配列を再構成します。
3. 除算用の係数（divider）を10倍していき、最大値の桁数ぶんだけ処理を繰り返します。

コード例

以下が実際のコードです。

const arr = [45, 2, 56, 2, 5, 6, 34, 1, 56, 89, 33];
const radixSort = (arr = []) => {
    const base = 10;
    let divider = 1;
    let maxVal = Number.NEGATIVE_INFINITY;
    while (divider === 1 || divider <= maxVal) {
        const buckets = [...Array(10)].map(() => []);
        for (let val of arr) {
            buckets[Math.floor((val / divider) % base)].push(val);
            maxVal = val > maxVal ? val : maxVal;
        }
        arr = [].concat(...buckets);
        divider *= base;
   };
    return arr;
};
console.log(radixSort(arr));

実行結果

コンソールには以下のように出力されます。

[
    1, 2, 2, 5, 6,
    33, 34, 45, 56, 56,
    89
]

このように、重複した値（2 や 56）も正しく保持されながら、配列全体が昇順に整列されていることが確認できます。降順にしたい場合は、最後に arr.reverse() を呼び出すだけで簡単に対応できます。