基数ソート

基数ソートは、数値を桁ごとに整列します。このレッスンは LSD（最下位桁優先）方式です。一の位、十の位、百の位の順に、各桁の値でバケットへ振り分けます。

各パスで同じバケット内の順序を保つと、前のパスで得た下位桁の順序が残ります。最大値の最上位桁まで処理すれば、数値全体が昇順になります。要素同士の大小比較は使いません。

基数ソートの仕組み

十進数では 0 から 9 までのバケットを用意します。現在の桁が一の位なら exp = 1、十の位なら exp = 10 です。値 x の対象桁は floor(x / exp) % 10 で求めます。

配列を先頭から読み、対応するバケットの末尾に要素を追加します。その後、バケット 0 から 9 の順に、中の要素を順序を保って回収します。exp を十倍して次の桁へ進みます。

同じ上位桁を持つ要素は、下位桁の順で並ぶ必要があります。各パスの安定性が、この順序を引き継ぎます。足りない上位桁は 0 として扱うため、8 の十の位は 0 です。

この実装はリスト形式のバケットへ追加して連結します。桁の度数表と累積和で配置する安定な計数ソートも、同じ役割を果たせます。

基数ソートのステップ

初期入力は [35, 42, 8, 32, 12, 25] です。最大値 42 は二桁なので、二回のパスを行います。

一の位。 バケット 2 に [42, 32, 12]、バケット 5 に [35, 25]、バケット 8 に [8] が入ります。各バケットでは入力順を保ちます。0 から 9 の順に回収すると、[42, 32, 12, 35, 25, 8] になります。この時点では数値全体の昇順ではなく、一の位だけが整列しています。

十の位。 今の配列を先頭から読みます。42 はバケット 4、32 は 3、12 は 1、35 は 3、25 は 2、8 は 0 に入ります。バケット 3 では 32 が 35 より前です。前のパスで得た一の位の順序が残っています。

回収すると [8, 12, 25, 32, 35, 42] になります。十の位が異なればバケット番号で順序が決まり、同じなら一の位の順序で決まります。これで整列完了です。

アニメーションでは対象桁、配列からバケットへの振り分け、バケットからの回収を追います。途中の配列が数値全体の昇順でなくても、処理済みの下位桁で整列していれば正しい状態です。

時間・空間計算量

n を要素数、d を最大値の桁数、b を基数とします。一回のパスは n 要素を振り分け、b 個のバケットを回収するので O(n + b) です。全体の時間は O(d·(n + b))、追加領域は O(n + b) です。

このレッスンでは b = 10 に固定するため、時間を O(d·n) と書けます。基数も変数として比較する場合は、バケットの費用を省略できません。

桁数が少ない整数に適しています。[7, 3, 9, 2, 50000] では、要素は五つでも五回のパスが必要です。上位桁のパスでは小さい値の多くがバケット 0 に入りますが、その読み書きも処理時間に含まれます。

境界条件

• 空配列：桁の処理を始めずに終了します。
• 一桁の正整数が一つ：一回のパスで同じ値を返します。
• 重複値：各パスが安定なので、元の順序を保ちます。
• 同じ十の位：[34, 31, 38, 32, 36, 35] は一の位のパスで昇順になります。十の位のパスでも順序は変わりませんが、処理は行います。
• 桁数が異なる値：存在しない上位桁を 0 として扱います。
• 負数：この非負整数向け実装では対象外です。符号を考慮した別の扱いが必要です。

よくある間違い

• 上位桁から同じ手順を行う：後の下位桁の整列が、上位桁で得た順序を崩します。MSD 方式では、上位桁で分けた各グループを個別に処理します。
• バケット内の順序を変える：十の位のバケット 3 で順序を逆転すると、[8, 12, 25, 35, 32, 42] となり、整列に失敗します。
• パス数を三回などに固定する：最大値に合わせて必要な桁数を求めます。
• 比較がないので常に速いと考える：桁数、基数、読み書きの回数も費用です。キーの性質に応じて比較ソートと選び分けます。