【アルゴリズム(JS実装)】Radix Sort

　どうも、わくばです！

　今日はRadix Sortです。Bucket Sortに似てますね。Radixというのは基数とか根とか底とかいくつか訳がありますが、この例ではn進法のnのことです。

　 Radix Sortを簡単に説明すると、例えば10進法で考えるなら

1. ０−９の計10個のバケットを準備する
2. 配列を全部スキャンし、各要素の1桁目の値について０−９に分類してバケットに入れる(345という要素ならバケット5に入れる)
3. 2を桁を上げて繰り返す。

 といった感じです。比較ベースではないタイプのソートです。

 コードはこんな感じになりました。

radixBaseはn進法のnのことです

const radixSort = (array, radixBase = 10) => {
    if (array.length < 2) {
        return array;
    }
    //有効数字がなくなるまで実行されるのでその範囲を知る必要がある
    const minVal = Math.min(...array);
    const maxVal = Math.max(...array);

    //以前僕が記事にしたcoutingSortとは少し違うので注意
    //Radixごとにソートするための関数
    const ctsForRadix = 
    (array, radixBase, significantDigit, minVal) => {
        //何個目のバケットか 
        let bcktIdx;

        //coutingSortのcounsに相当
        //要は出現回数をカウントする
        const counts = [];
        const mirror= [];

        //十進法であればradixBaseは10
        //10個のバケットを作る
        for (let i = 0; i < radixBase; i++) { 
            counts[i] = 0;
        }

        //各値がどのバケットに当たるかを計算しカウントする
        for (let i = 0; i < array.length; i++) { 
            bcktIdx = Math.floor((
                (array[i] - minVal) / significantDigit
                ) % radixBase); 
            counts[bcktIdx]++; 
        }

        /**
        ここからが僕の記事のcountingSortと少し違う
        以下の処理は各バケットの第一項が、
        出力する配列の何項目に当たるかを計算している
        **/
        for (let i = 1; i < radixBase; i++) { 
            counts[i] += counts[i - 1];
        }

        //カウント情報からソートを実行
        for (let i = array.length - 1; i >= 0; i--) { 
            bcktIdx = Math.floor((
                (array[i] - minVal) / significantDigit
                ) % radixBase ); 
            mirror[--counts[bcktIdx]] = array[i]; 
        }
        for (let i = 0; i < array.length; i++) { 
            array[i] = mirror[i];
        }
        return array;
    }


    //まずは１桁目でソート
    let significantDigit = 1; 
    while ((maxVal - minVal) / significantDigit >= 1) { 
        array = ctsForRadix(array, radixBase, significantDigit, minVal); 
        //桁を上げる
        significantDigit *= radixBase; 
    }
    return array;
}
console.log(radixSort([1,5888,25,438,0,9,6,5,44,7,8,44])

>>>[
      0,    1,  5,  6,  7,
      8,    9, 25, 44, 44,
    438, 5888
    ]

　オーダーとしては、サイズnの配列をk進数でソートすると、単純にk回分配するので\(O(nk)\)と考えられます。

　今日は以上です。

　誤っている点や質問などありましたらぜひコメントください。

　では。