基数ソートの仕組みを徹底解説！アニメーションで学ぶ「桁を利用する」ソート【ソートアルゴリズム入門】#14

カウンティングソートの「弱点」

　前回の記事では、「比較しないソート」の代表格であるカウンティングソートを紹介しました。

「0点〜100点」のような、データのとりうる値の範囲（\(k\)が狭い場合は \(O[N+k]\) という驚異的な速さを誇りました。

カウンティングソートの仕組みを徹底解説！アニメーションで学ぶ「数え上げ」ソート【ソートアルゴリズム入門】#13

カウンティングソート(数え上げソート)について、実際にソート手順を試せるツール付きでどのような仕組みなのか紹介します。

しかし、カウンティングソートには「もしデータの範囲(k)が非常に大きかったら？」という弱点がありました。 例えば、ソートしたいデータが「0〜10億」までの数値だった場合、 「10億個のバケツ（カウント用配列）」 を用意する必要があり、現実的ではありません。

では、比較ソートの限界 \(O[n \log n] \) を超えるのは夢物語なのでしょうか？

いいえ、その弱点を「賢いアイデア」で克服し、高速性を実現するのが今回紹介する「基数ソート（Radix Sort）」です。

基数ソート実行アニメーション

この記事では、基数ソートがどのようにしてカウンティングソートの「バケツ」のアイデアを応用し、「10億」のような大きな数でも効率的にソートできるのか、その仕組みを解説していきます。

1. 基数ソート（Radix Sort・バケツソート）とは？

基数ソートも「比較しないソート」の一種です。 その最大の特徴は、「一度に全部を比べようとしない」ことにあります。

基数ソートは、データを「桁（けた）ごと」に分けてソートします。 一般的に使われる LSD (Least Significant Digit) 基数ソートは、以下の手順で動作します。

1. 1の位（一番下の桁）だけを見て、数を並び替える。
2. 次に、10の位だけを見て、数を並び替える。
3. 次に、100の位だけを見て、数を並び替える。
4. これを、一番大きな数の一番上の桁（最上位桁）が終わるまで繰り返す。

「そんなことで、本当に全体がソートされるの？」と思うかもしれません。 これには一つ、非常に重要な「お約束」があります。

お約束：各「桁」でソートするとき、必ず「安定ソート」を使うこと。

安定ソートとは、「同じ値（今回の場合は同じ桁の数字）だった場合、元の順序を崩さない」という性質を持つソートのことです。

そして、この「安定ソート」として、カウンティングソートが完璧なのです。 なぜなら、「1つの桁」だけを見れば、その範囲は必ず「0〜9」の10種類（(k=10))しかありません。これはカウンティングソートが最も得意とする「範囲が狭い」状況です。

2. 基数ソートで「数字のリスト」を並び替えたら？

では、実際に [ 170, 45, 75, 90, 802, 24, 2, 66 ] というリストをソートする手順を見ていきましょう。 （分かりやすくするため、2 は 002、24 は 024 のように、最大の桁数（3桁）に合わせます）

ステップ1：【1の位】でソートする

まず、各数値の「1の位」 [ 0, 5, 5, 0, 2, 4, 2, 6 ] に注目します。 これを「0〜9」のバケツ（カウンティングソート）を使って並び替えます。

• 0 のバケツ: [ 170, 90 ] (元の順序を維持)
• 2 のバケツ: [ 802, 2 ] (元の順序を維持)
• 4 のバケツ: [ 24 ]
• 5 のバケツ: [ 45, 75 ] (元の順序を維持)
• 6 のバケツ: [ 66 ]

バケツから順番に取り出すと、リストはこうなります。 1回目ソート後: [ 170, 90, 802, 2, 24, 45, 75, 66 ]

ステップ2：【10の位】でソートする

次に、ステップ1の結果のリスト [ 170, ... ] を使って、「10の位」 [ 7, 9, 0, 0, 2, 4, 7, 6 ] に注目します。 これを再び「0〜9」のバケツで並び替えます。

• 0 のバケツ: [ 802, 2 ] (1回目の結果 802 が 2 より先だったので、この順序を維持)
• 2 のバケツ: [ 24 ]
• 4 のバケツ: [ 45 ]
• 6 のバケツ: [ 66 ]
• 7 のバケツ: [ 170, 75 ] (1回目の結果 170 が 75 より先だったので、この順序を維持)
• 9 のバケツ: [ 90 ]

バケツから順番に取り出すと、リストはこうなります。 2回目ソート後: [ 802, 2, 24, 45, 66, 170, 75, 90 ]

ステップ3：【100の位】でソートする

最後に、ステップ2の結果のリスト [ 802, ... ] を使って、「100の位」 [ 8, 0, 0, 0, 0, 1, 0, 0 ] に注目します。 これをバケツで並び替えます。

• 0 のバケツ: [ 2, 24, 45, 66, 75, 90 ]
  • （注目！2回目の結果の順序 [2, 24, 45, 66, 75, 90] がそのまま維持されています。これが安定ソートでなければいけない理由です。）
• 1 のバケツ: [ 170 ]
• 8 のバケツ: [ 802 ]

バケツから順番に取り出すと、リストは完成です。 3回目ソート後: [ 2, 24, 45, 66, 75, 90, 170, 802 ]

「安定ソート」のおかげで、「上の桁」をソートしても、「下の桁」ですでにソートした結果が崩れないのです。これが基数ソートの仕組みです。

3. 基数ソートの動きを見てみよう！

基数ソートで並び替えを試せます。 「ソート」ボタンを押すと、「1の位」「10の位」「100の位」と、バケツが切り替わりながらソートされていく様子を観察してみてください。

4. 基数ソートの疑似コード (ソートの手順)

基数ソートは、「桁ごとの安定ソート」を繰り返すループとして表現できます。

// L: ソートしたいリスト
// maxVal: リスト内の最大値 (例: 802)
algorithm RadixSort(L, maxVal) is
  
  // 処理する桁 (1の位からスタート)
  digitPlace ← 1 
  
  // 最大値 (802) を超える桁 (1000) になるまでループ
  while maxVal / digitPlace > 0 do
    
    //
    // digitPlaceの桁 (1の位、10の位...) に基づいて
    // リストLを「安定ソート」する。
    // (内部的には0〜9のバケツを持つカウンティングソートが動く)
    //
    L ← stableSortByDigit(L, digitPlace)
    
    // 次の桁へ (1 -> 10 -> 100)
    digitPlace ← digitPlace * 10
    
  end
  
  return L
end

// ------------------------------------
// (参考) stableSortByDigit の内部イメージ
// L: [170, 45], digitPlace: 10 (10の位)
algorithm stableSortByDigit(L, digitPlace) is
  buckets ← 0〜9の10個の空のリスト
  
  for val in L do
    // (45 / 10) % 10 = 4.5 % 10 = 4 
    // (170 / 10) % 10 = 17 % 10 = 7
    digit ← floor(val / digitPlace) % 10 
    buckets[digit].append(val)
  end
  
  // バケツ0から9の順に連結して返す
  return concatenate(buckets[0], buckets[1], ..., buckets[9])
end

まとめ

• 基数ソートは、「比較しないソート」であり、カウンティングソートの応用版。
• カウンティングソートの弱点だった「広すぎるデータの範囲」を、「桁ごと」に分けることで克服した。
• 「1の位」「10の位」…と、下の桁から順番に「安定ソート」（主にカウンティングソート）を適用する。
• 計算量は \(O[d(n+k)]\) となる。
  • \(n\): データの数
  • \(d\): 最大値の桁数（例：10億なら (d=10)）
  • \(k\): 1つの桁の基数（例：10進数なら (k=10)）
• \(d\) と\(k\) がデータ数 (N) に比べて十分に小さければ、実質 \(O[n]\) に近い速度で動作し、比較ソートの\ (O[n \log n]\) の壁を理論的に超えることができる。

これで、ソートアルゴリズムの基本から高速化、そして「比較」の壁を超える方法まで、一通り学ぶことができました。次回は、一旦、今まで出てきたソートについてその速度や特性についてまとめて比較してこのシリーズひとまずの締めとしようと思います。

 Loading ...

(関連記事) 前の記事 (カウンティングソート)

カウンティングソートの仕組みを徹底解説！アニメーションで学ぶ「数え上げ」ソート【ソートアルゴリズム入門】#13

カウンティングソート(数え上げソート)について、実際にソート手順を試せるツール付きでどのような仕組みなのか紹介します。

(関連) 比較ソートの限界

O[n log(n)] の壁を超える！「比較しないソート」【ソートアルゴリズム入門】#12

比較しないソートとは？比較ソートの計算量O[n log(n)]を超える別のアプローチについてその導入を紹介します。

次の記事 : ソートアルゴリズム入門で紹介したソートの比較まとめ

【総まとめ】ソートアルゴリズム O[n^2] から O[n] への道すじ【ソートアルゴリズム入門】#15

ソートアルゴリズム入門シリーズの総まとめ。バブルソートから基数ソートまで、計算量、安定性、特徴を一覧表で徹底比較。結局どれを使えばいいのかも解説します。

ここまで読んでいただきありがとうございます。 では、次の記事で。 lumenHero