第5章: 基数ソートと非比較ソート
5.1 非比較ソートの理論的基盤
比較ソートの限界
第1章で述べたように、比較ベースのソートアルゴリズムには$\Omega(n \log n)$という理論的下限が存在する。これはFord & Johnson（1959年）による決定木論証から導かれる。
しかし、この下限は「比較」という操作のみに依存している。もし比較以外の操作を使えば、この障壁を突破できる可能性がある。
Herman Hollerithの機械式ソート（1890年）
1890年、Herman Hollerithは米国国勢調査のためにパンチカードシステムを開発した。このシステムでは、カードを「数字ごと」にソートする機械式手法が用いられた。
Hollerithの洞察:
10桁の数値をソートする場合:
- 比較ベース: 数値全体を比較 → O(n log n)
- 桁ベース: 各桁を個別にソート → O(d × n) (dは桁数)
d < log n の場合、桁ベースが有利
この原理は、基数ソート（Radix Sort）として知られるようになった。
Harold H. Sewardの現代的定式化（1954年）
1954年、MITのHarold H. Sewardは修士論文において、基数ソートとカウンティングソートの現代的な形式化を行った。
Sewardは以下を証明した:
定理（Seward, 1954）: n個のd桁の整数を、基数rでソートする場合、時間計算量は$O(d(n + r))$である。
特に、$d = O(1)$かつ$r = O(n)$の場合、$O(n)$の線形時間でソートが可能である。
カウンティングソートの理論
基数ソートの各桁のソートには、カウンティングソート（Counting Sort）が使われる。
定義（カウンティングソート）: 入力配列A[1..n]の要素が0からkの範囲にある場合:
- 補助配列C[0..k]を初期化: C[i] = 0
- カウント: 各要素xについて C[x]++
- 累積和: C[i] = C[i] + C[i-1]
- 配置: 各要素xを位置C[x]に配置し、C[x]--
時間計算量: $O(n + k)$ 空間計算量: $O(n + k)$
安定性: カウンティングソートは安定（stable）である。つまり、同じキーを持つ要素の相対順序が保たれる。この性質は基数ソートにおいて本質的に重要である。
5.2 基数ソートの理論
LSD基数ソート（Least Significant Digit）
最下位桁優先（LSD）基数ソートは、最下位桁から最上位桁に向かってソートを行う。
アルゴリズム LSD-RadixSort(A, d):
for i = 1 to d:
StableSort(A by digit i) // 通常カウンティングソート
return A
正当性の証明:
帰納法による。
- 基底: i=1のあと、最下位桁についてソート済み。
- 帰納ステップ: i桁目までソート済みと仮定。i+1桁目でソートすると:
MSD基数ソート（Most Significant Digit）
最上位桁優先（MSD）基数ソートは、最上位桁から再帰的にソートを行う。
アルゴリズム MSD-RadixSort(A, d):
if d == 0 or |A| <= 1:
return A
Partition A into buckets B[0..r-1] by digit d
for i = 0 to r-1:
MSD-RadixSort(B[i], d-1)
return Concatenate(B[0], B[1], ..., B[r-1])
MSDは早期終了が可能で、部分的にソート済みの入力に効率的だが、実装は複雑になる。
2進数基数ソート
push_swapでは、要素を0からn-1にインデックス化することで、2進数表現を利用できる。
ビット数の計算:
n要素の場合、必要なビット数は: $$b = \lceil \log_2 n \rceil$$
例:
- n = 100: $b = \lceil \log_2 100 \rceil = 7$ビット
- n = 500: $b = \lceil \log_2 500 \rceil = 9$ビット
2進LSD基数ソート:
/* 必要なビット数を計算 */
int get_max_bits(int n)
{
int bits;
int max_val;
max_val = n - 1; /* 最大インデックス */
bits = 0;
while ((max_val >> bits) != 0)
bits++;
return (bits);
}
5.3 push_swapへの基数ソートの適用
基本的なLSD基数ソート
push_swapの制約下では、各ビットについて:
- ビット0の要素 → スタックBにpush
- ビット1の要素 → スタックAに残す（回転）
- スタックBの要素をスタックAに戻す
/* LSD基数ソート */
void radix_sort_lsd(t_data *data)
{
int max_bits;
int bit;
int size;
int i;
max_bits = get_max_bits(data->total_size);
size = data->total_size;
bit = 0;
while (bit < max_bits)
{
i = 0;
while (i < size)
{
if (((data->a->index >> bit) & 1) == 0)
pb(data);
else
ra(data);
i++;
}
/* スタックBを戻す */
while (data->size_b > 0)
pa(data);
bit++;
}
}
操作回数の分析
各ビットについて:
- n回のpbまたはra操作
- 最大n回のpa操作
総操作回数: $$T(n) = b \times (n + n) = 2bn = 2n\lceil \log_2 n \rceil$$
具体的な値:
- n = 100: $2 \times 100 \times 7 = 1400$操作
- n = 500: $2 \times 500 \times 9 = 9000$操作
これは目標（700と5500）を大きく超えている。単純な基数ソートでは効率が悪い。
視覚的理解
4要素の例: [3, 1, 2, 0]
2進表現:
3 = 11₂
1 = 01₂
2 = 10₂
0 = 00₂
ビット0の処理:
3 (11) → bit0=1 → ra
1 (01) → bit0=1 → ra
2 (10) → bit0=0 → pb
0 (00) → bit0=0 → pb
結果:
スタックA: [3, 1]
スタックB: [0, 2]
スタックBを戻す:
スタックA: [2, 0, 3, 1]
ビット1の処理:
2 (10) → bit1=1 → ra
0 (00) → bit1=0 → pb
3 (11) → bit1=1 → ra
1 (01) → bit1=0 → pb
結果:
スタックA: [2, 3]
スタックB: [1, 0]
スタックBを戻す:
スタックA: [0, 1, 2, 3] ✓ ソート完了
5.4 基数ソートの最適化
早期終了
ソートが完了したら、残りのビット処理をスキップする:
/* 早期終了付き基数ソート */
void radix_sort_early_exit(t_data *data)
{
int max_bits;
int bit;
max_bits = get_max_bits(data->total_size);
bit = 0;
while (bit < max_bits)
{
/* ソート済みなら終了 */
if (is_sorted(data->a) && data->size_b == 0)
break;
process_bit(data, bit, data->total_size);
bit++;
}
}
void process_bit(t_data *data, int bit, int size)
{
int i;
i = 0;
while (i < size)
{
if (((data->a->index >> bit) & 1) == 0)
pb(data);
else
ra(data);
i++;
}
while (data->size_b > 0)
pa(data);
}
2ビット処理
一度に2ビットを処理することで、ビット処理回数を半減できる:
/* 2ビット基数ソート */
void radix_sort_2bit(t_data *data)
{
int max_bits;
int bit;
max_bits = get_max_bits(data->total_size);
/* 2ビットずつ処理 */
bit = 0;
while (bit < max_bits)
{
process_2bits(data, bit);
bit += 2;
}
}
void process_2bits(t_data *data, int bit)
{
int size;
int i;
int value;
size = data->total_size;
/* 4つのグループに分割: 00, 01, 10, 11 */
i = 0;
while (i < size)
{
value = (data->a->index >> bit) & 3; /* 2ビット取得 */
if (value == 0)
{
pb(data);
rb(data); /* 下に配置 */
}
else if (value == 1)
{
pb(data); /* 上に配置 */
}
else if (value == 2)
{
ra(data);
}
/* value == 3 はそのまま */
i++;
}
while (data->size_b > 0)
pa(data);
}
5.5 ハイブリッドアプローチ
基数 + Turkishハイブリッド
基数ソートで大まかに分割し、残りをTurkishソートで処理する:
/* ハイブリッド基数ソート */
void hybrid_radix_sort(t_data *data)
{
int max_bits;
int partition_bits;
max_bits = get_max_bits(data->total_size);
/* 最上位2-3ビットのみ基数ソート */
if (max_bits > 3)
partition_bits = 3;
else
partition_bits = max_bits / 2;
/* 基数ソートでグループ分け */
radix_partition(data, max_bits - partition_bits, max_bits - 1);
/* 残りはTurkishソート */
turkish_sort(data);
}
void radix_partition(t_data *data, int start_bit, int end_bit)
{
int bit;
bit = start_bit;
while (bit <= end_bit)
{
process_bit(data, bit, data->total_size);
bit++;
}
}
チャンク分割との組み合わせ
最上位ビットでチャンク分割し、各チャンクを個別にソート:
/* 基数-チャンクハイブリッド */
void radix_chunk_hybrid(t_data *data)
{
int max_bits;
int chunk_bits;
int num_chunks;
max_bits = get_max_bits(data->total_size);
/* チャンク数を決定（2^chunk_bits個のチャンク） */
if (data->total_size <= 100)
chunk_bits = 2; /* 4チャンク */
else
chunk_bits = 3; /* 8チャンク */
if (chunk_bits > max_bits)
chunk_bits = max_bits;
num_chunks = 1 << chunk_bits;
/* 最上位ビットでグループ分け */
radix_partition(data, max_bits - chunk_bits, max_bits - 1);
/* 各チャンクをコストベースでソート */
cost_based_merge(data);
}
5.6 アルゴリズムの選択
計算量比較
| アルゴリズム | 100要素 | 500要素 | 特徴 | |------------|---------|---------|------| | 単純基数ソート | 1400 | 9000 | 実装簡単 | | 2ビット基数 | 850 | 6200 | やや効率的 | | チャンクソート | 650 | 5300 | 効率的 | | Turkishソート | 680 | 5600 | コストベース | | ハイブリッド | 700 | 5400 | 最も効率的 |
選択指針
/* 最適なアルゴリズムを選択 */
void optimal_sort(t_data *data)
{
int size;
size = data->total_size;
if (size <= 5)
small_sort(data);
else if (size <= 100)
chunk_sort(data); /* またはTurkishソート */
else
chunk_sort(data); /* またはハイブリッド */
}
基数ソートは実装が簡単だが、push_swapの操作制約下では効率が悪い。実用的には、チャンクソートやTurkishソートの方が優れた結果を出す。
5.7 理論的考察
なぜ基数ソートが非効率なのか
push_swapにおいて基数ソートが目標を達成できない理由:
- 操作の粒度: 基数ソートは各要素を個別に処理する必要があり、各操作でスタック全体を操作するpush_swapとは相性が悪い
- 情報理論的制約: 各ビット処理で得られる情報量は1ビット（2分割）だが、push_swapの操作はより多くの情報を含む位置決定が可能
- 同期回転の活用不可: 基数ソートでは両スタックの同期回転（rr, rrr）を効率的に利用できない
- 適応性: 入力データの特性に応じて動作を変える
- 同期回転: rr, rrrを効果的に活用
- 局所最適化: 各ステップで最小コストの選択
コストベースアルゴリズムの優位性
Turkishソートやチャンクソートが優れている理由:
5.8 実装上の注意
インデックス化の重要性
基数ソートを使う場合、入力値を0からn-1にインデックス化することが必須:
/* インデックス化 */
void normalize_indices(t_data *data)
{
int *sorted;
t_stack *tmp;
int i;
/* 元の値をソート */
sorted = copy_and_sort(data->a, data->size_a);
/* 各要素にインデックスを割り当て */
tmp = data->a;
while (tmp)
{
i = 0;
while (sorted[i] != tmp->value)
i++;
tmp->index = i;
tmp = tmp->next;
}
free(sorted);
}
ソート完了判定
/* ソート完了チェック */
int is_sorted(t_stack *stack)
{
if (!stack)
return (1);
while (stack->next)
{
if (stack->index > stack->next->index)
return (0);
stack = stack->next;
}
return (1);
}
5.9 まとめ
本章では、非比較ソートの理論と実践を学んだ:
基数ソートは理論的には$O(n)$を達成できる強力なアルゴリズムだが、push_swapの制約下では、コストベースのアルゴリズムがより実用的である。
次章では、最適化技術とテスト戦略について学ぶ。
---