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

計数ソート:キーの個数から出力位置を決める

整数キーの範囲を利用し、累積度数で安定に配置する手順とO(n+k)の前提を確かめる。

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

更新日

この記事の目次
  1. 比較の代わりにキーの範囲を使う
  2. 2a、0、2b、1を配置する
  3. 累積配列の意味を固定する
  4. 範囲とレコードの扱いを検証する
  5. この記事をロゲイアに質問する理解を確かめる

比較の代わりにキーの範囲を使う

計数ソートは整数キーが0からk−1の範囲にあるとき、各キーの個数を長さkの配列へ数えます。比較だけで大小を判断する整列ではなく、キーを配列の添字として使うため、比較整列の下界と矛盾しません。負のキーも最小値を引けば扱えますが、必要な領域は値の種類数ではなく最大値と最小値の幅で決まります。要素数が少なくてもキーが巨大な範囲へ散らばる場合には、この方法が適しているとは限りません。整数の範囲検査は数え始める前に必要です。

2a、0、2b、1を配置する

[2a,0,2b,1]の個数はキー0、1、2の順に[1,1,2]です。各キーより小さい要素の個数は[0,1,2]となるので、0は出力位置0、1は位置1、最初の2は位置2へ置けます。入力を左から走査し、そのキーの次の空き位置を一つ進めれば、2bは位置3へ入り[0,1,2a,2b]になります。個数だけからキーを並べ直す方式とは違い、レコード全体を出力へ移すので、同値キーの付随情報と出現順を保つことができます。

累積配列の意味を固定する

累積配列に、キー未満の個数を入れる方式では左から配置し、キー以下の個数を入れる方式では右から配置するのが典型です。後者なら配置前にそのキーの個数を一つ減らして添字にします。この二つの約束を混ぜると、同値キーの順序や出力位置が崩れます。時間は入力の集計、累積、配置を合わせてO(n+k)、安定な出力配列を使う形では補助領域もO(n+k)です。キーだけを復元する別の形と、レコードを安定に整列する形を区別してください。

範囲とレコードの扱いを検証する

例えば100件のキーが0と10億だけなら、長さ10億超のカウント配列を確保する費用が問題になります。疎な辞書へ数えるだけでは、そのキーを順番に出すための別の整列が必要で、元のO(n+k)の説明とは別物になります。件数がカウンタ型の最大値を越えないこと、オフセット計算がオーバーフローしないことも確認します。成績の整数点や小さい文字集合の分類のように範囲が小さい用途で有効で、LSD基数ソートの安定な一桁処理にもつながります。

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

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

CS基礎を固める · STEP 10

学習コースから次を選ぶ