アルゴリズム・データ構造図鑑 · 基礎から応用へ

基数ソート:一桁ずつの安定な整列を重ねる

LSD方式で一の位から処理し、安定性が複数桁の順序をつなぐ理由と桁数・基数の費用を学ぶ。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 一の位から並べるLSD方式
  2. 21、13、12を二回で整列する
  3. O(d(n+r))の内訳
  4. 符号と長さに注意する
  5. この記事をロゲイアに質問する理解を確かめる

一の位から並べるLSD方式

LSD基数ソートは、キーを基数rのd桁として表し、下位の桁から上位の桁へ安定に整列します。一桁を処理するたび、処理済みの下位部分について順序が完成している、という不変条件があります。文字列でも固定長で文字の順序が定まれば同じ考えを使えます。ただし数値としての順序と文字コード順は別なので、どちらを求めるかを先に決めます。桁を取り出す操作の費用と、キーを一定幅で表現できるという前提も時間評価に含める必要があります。

21、13、12を二回で整列する

十進二桁の[21,13,12]を一の位で安定に整列すると[21,12,13]です。次に十の位で安定に整列すると、十の位が1である12と13の順番はそのまま残り、[12,13,21]になります。二回目に同じ十の位のグループを自由に並べ替えると、一回目に作った一の位の順序を壊しかねません。上位の桁を優先しつつ、同じ上位の桁の内部では下位の桁が順序を決めるという辞書式の構造を、安定な各パスが実現しています。

O(d(n+r))の内訳

一桁の処理を安定な計数ソートで行えば、その時間はO(n+r)です。これをd回行うので全体はO(d(n+r))になります。dもrも定数扱いできる場面では要素数に対して線形と説明できますが、任意精度整数や長い文字列ではdが増えます。rを大きくすればパス数は減るもののカウント配列が大きくなるため、単純に最大の基数を選べばよいわけではありません。出力配列とカウント配列の補助領域は一般にO(n+r)です。

符号と長さに注意する

符号付き整数のビット列を符号なしの値としてそのまま並べると、負数と非負数の順序が数値順と一致しません。符号ビットを変換するなど、表現に応じた処理が必要です。可変長の文字列には終端の扱いを決めるか、上位桁から分けるMSD方式などを検討します。MSD方式とLSD方式では部分問題の作り方が異なり、すべての性質をそのまま移せません。空入力、同じ桁が続く入力、最大値・最小値を試し、安定性と境界の両方を確認します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ