【きすうソート】
基数ソート とは？
最終更新:
💡 桁ごとの箱に分けて、順序を積み重ねる
数値や文字列の桁ごとに分類して並べ替えるソートです。下の桁から進めるLSD方式では、同じ桁の値の順序を保って次の桁へ進めることが重要です。
📌 このページのポイント
ひよこ 比較しないで、どうやって並べるの？
ペンギン先生 ここでは0以上の整数を、10進数の下の桁から並べるLSD方式で考えよう。1の位で0〜9の箱に振り分け、箱を小さい順に取り出す。次は10の位、と繰り返すんだ。要素同士の大小比較で順番を決める方法とは違うよ。
ひよこ 具体例で見たいな。
ペンギン先生 [21,12,11,22]なら、1の位で分けると[21,11,12,22]。次に10の位で分けると[11,12,21,22]になるよ。同じ桁の値なら、その直前の並び順を保って取り出すのが大事なんだ。
ひよこ 同じ値の順序を保つのは、なぜ？
ペンギン先生 10の位が同じ11と12では、1の位で決めた11→12の順序を残したいからだよ。これを安定な振り分けという。桁がない部分は0として扱うなど、データの表現も揃える必要があるんだ。
ひよこ 普通のソートより必ず速い？
ペンギン先生 必ずではないよ。各桁をカウンティングソートで処理するなら、n個・d桁・分類数bでO(d×(n+b))と考えられる。dとbを固定できればnに比例するけれど、桁数やメモリ、実装も影響する。入力の性質を使うので、比較だけを使うソートの下限とは条件が違うんだ。
ひよこ 文字列や負の数にも使える？MSDって何？
ペンギン先生 文字列や符号付き整数も、長さ・文字の順序・符号を扱う実装なら使えるよ。上の桁からグループを分けるのがMSD方式。どの基数ソートでも下の桁から始めるわけではない。図は非負整数のLSDの例として見てね。
まとめ：ざっくりこれだけ覚えればOK！
「基数ソート」って出てきたら「桁ごとに振り分けて並べるソート」と思えばだいたいOK！
📖 おまけ：英語の意味
「Radix Sort」 ＝ 基数を使った並べ替え
💬 radixは数の基数のこと。10進数なら各桁に0〜9の値を使うので、基数は10だよ。