要素同士を比較しない！？基数ソートを解説！

前回は、二つ目の要素同士を比較しないソートとして、分布数え上げソートを解説した。

前々回のビンソートもそうだったのだが、データのとり得る範囲が大きいと…つまり、箱のサイズが大きいと効率が悪くなってしまった。

今回は、そんなデメリットを改善できる、基数ソートというものをご紹介しよう。

なお、今回の基数ソートには、前回の分布数え上げソートの知識が必要となる。

「それ何？」という方は、復習をしておこう。

シノ

考え方はとても単純だよ！

基数ソート

では、いつもの通りまずはデータの制約条件から。

• 要素が整数(自然数)

これだけだ。

考え方も非常に単純。

まず、1の位だけ見てソートを行う。

次に、10の位を見て、安定なソートを行う。

以降同じように、下から順番に特定の桁だけを見て安定なソートを行っていくだけだ。

これも具体例で見ていこう。

以下のデータをソートする。

では、まず1の位だけ見てソートをしていく。

すると、以下のように並び替えができる。

次に、10の位でソートをしてみよう。

ただし、ここでは安定なソートをすることがポイント。

すると…

綺麗に並んでくれたのが分かるだろうか。

このように、下の桁から順番に安定なソートを繰り返すことで、最終的にソートが完了する。

では、この一桁の中でどんなソートをするかだが、ここに分布数え上げソートが出てくる。

その分布数え上げソートって何？という方は、以下の記事で解説しているので見て欲しい。

要素同士を比較しない！？分布数え上げソートを解説！ | Shino’s Mind Archive

分布数え上げソートを使う理由は、計算量が絡んでくるので、そこで解説しよう。

基数ソートの計算量

一応、基数ソートも計算量は\(O(n)\)なのだが、これには条件がある。

というのも、結局は各桁で行うソートに左右されてしまうのだ。

そのソートを複数回繰り返すので、当然と言えば当然だ。

前回まで解説してきたビンソートや分布数え上げソートは、計算量は\(O(n)\)だった。

それに対し、その他のソートは早くても\(O(n \log(n))\)。

それであれば、より高速なもの…つまり、計算量が\(O(n)\)を使うべきだろう。

そして、必要な条件として、安定であることが求められた。

これに合致するのは、分布数え上げソートだ。

というわけで、分布数え上げソートを使おうという話になる。

すると、箱の大きさは必ず10で良くなり、計算量は\(O(n)\)となる。

つまり、それを桁数だけ繰り返すので、最終的な基数ソートの計算量も\(O(n)\)として考えられるのだ。

基数ソートのサンプルプログラム

最後に、サンプルプログラムを提示しておこう。

いつもながらに言語はJavaScript、入力はdata配列で、これを直接並び替える。

function RadixSort(data){
    let box = [];

    let tmp = [];
    let keta = 1;

    while(!check(data)){
        for(let i = 0; i < 10; i++){
            box[i] = 0;
        }

        for(let i = 0; i < data.length; i++){
            box[getNumber(data[i], keta)]++;
        }

        for(let i = 0; i < 9; i++){
            box[i + 1] += box[i];
        }

        for(let i = data.length - 1; i >= 0; i--){
            box[getNumber(data[i], keta)]--;
            tmp[box[getNumber(data[i], keta)]] = data[i]
        }

        for(let i = 0; i < data.length; i++){
            data[i] = tmp[i];
        }

        keta *= 10;
    }
}

function getNumber(data, keta){
    return Math.floor((data % (keta * 10)) / keta);
}

function check(data){
    for(let i = 0; i < data.length - 1; i++){
        if(data[i] > data[i + 1]){
            return false;
        }
    }
    return true;
}

今回の処理としては、下の桁から順番にソートをしていき、全部綺麗に並び終えていたら終了するという形にしてある。

その、並び替えが完了しているかどうかを判定するのがcheck()関数だ。

そして、ある数値と、どの位かを入力することで、その位の値を取得するgetNumber()関数も作った。

これらを使って、そのまま桁ごとに分布数え上げソートをしている、という形になる。

前回のサンプルも併せて見てもらえれば、より理解が深まるだろう。

おわりに

今回は、基数ソートを解説した。

考え方自体は非常に単純だが、別のソートも必要になるということには気を付けよう。

さて、これまで色々なソートを解説してきたが、これでいったん完結となる。

これ以外にも、面白いソートなどあったら、別途解説するとしよう。