第4章: 大量データソート戦略
4.1 分割統治法の起源
ガウスとナポレオンの時代
1805年、数学者Carl Friedrich Gaussは膨大な天文観測データを処理するため、直感的な分割統治法を用いていた。しかし、これがアルゴリズムとして形式化されるまでには、さらに140年の歳月を要した。
John von Neumannのマージソート（1945年）
1945年、EDVACの設計に携わっていたJohn von Neumannは、計算機でのデータソートに関する最初の形式的アルゴリズムを考案した。彼のマージソート（Merge Sort）は、分割統治法（Divide and Conquer）を計算の文脈で初めて明確に定式化したものである。
von Neumannの洞察:
問題P(n)を解くために:
1. 分割: Pを2つの部分問題P(n/2)に分ける
2. 征服: 各部分問題を再帰的に解く
3. 統合: 部分解を結合して全体解を得る
この原理は、マージソートの時間計算量を次の漸化式で表現する:
$$T(n) = 2T(n/2) + O(n)$$
マスター定理により、これは$O(n \log n)$に解ける。
Tony Hoareのクイックソート（1962年）
1962年、英国のコンピュータ科学者Tony Hoareは、よりエレガントな分割統治法としてクイックソート（Quicksort）を発表した（"Quicksort", Computer Journal, 5(1), 1962）。
Hoareの革新は「ピボット（pivot）」の概念にあった:
Quicksort(A, lo, hi):
if lo < hi:
p = Partition(A, lo, hi) // ピボットを正しい位置に配置
Quicksort(A, lo, p - 1)
Quicksort(A, p + 1, hi)
クイックソートの平均時間計算量は$O(n \log n)$だが、最悪時は$O(n^2)$となる。しかし、実際の入力に対しては、その定数因子の小ささから、ほとんどの場合でマージソートより高速である。
計算量の数学的解析
Donald Knuthは"The Art of Computer Programming"（Vol. 3, 1973）において、クイックソートの平均比較回数を厳密に導出した:
$$C_n = 2(n+1)H_n - 4n \approx 1.386n\log_2 n$$
ここで$H_n = \sum_{k=1}^{n}\frac{1}{k}$は調和級数である。
この解析は、ピボット選択がランダムである場合の期待値を与える。最適なピボット（中央値）を常に選べれば、比較回数は$n\log_2 n$に近づく。
4.2 バケットソートと分布ソート
Harold H. Sewardの着想（1954年）
1954年、MITの大学院生Harold H. Sewardは、修士論文においてバケットソート（Bucket Sort）と基数ソート（Radix Sort）の現代的定式化を行った。
Sewardの洞察は、入力の分布に関する知識を利用することで、比較ベースソートの下限$\Omega(n \log n)$を突破できるというものだった。
バケットソートの原理:
BucketSort(A, k):
1. k個の空バケットを用意
2. 各要素を適切なバケットに分配
3. 各バケットを個別にソート
4. バケットを順に連結
入力が一様分布に従う場合、各バケットには平均$n/k$個の要素が入る。バケット内ソートに挿入法を使うと:
$$T(n) = O(n) + \sum_{i=0}^{k-1}O\left(\frac{n}{k}\right)^2 = O(n + \frac{n^2}{k})$$
$k = n$とすれば、$O(n)$の期待時間計算量が達成される。
チャンクソートへの応用
push_swapにおける「チャンクソート」は、バケットソートの変形である。スタックという制約下で、要素をチャンク（バケット）に分割し、順次処理する。
チャンク数の理論的最適化:
n個の要素をk個のチャンクに分割する場合を考える。各要素をチャンクに移動するコストと、チャンク内の整理コストのトレードオフがある。
チャンクへの分配コスト: 各要素に対して平均$O(n/k)$回転が必要 チャンク整理コスト: 各チャンク内で平均$O((n/k)^2)$操作が必要
総コストの期待値: $$C(k) = O(n \cdot \frac{n}{k}) + O(k \cdot (\frac{n}{k})^2) = O(\frac{n^2}{k} + \frac{n^2}{k})$$
これを最小化するには$k \approx \sqrt{n}$が最適となる。
| n | 最適チャンク数 $k \approx \sqrt{n}$ | 経験則 | |---|-----------------------------------|--------| | 100 | 10 | 15-20 | | 500 | 22 | 35-45 |
経験則が理論値より大きいのは、push_swap固有の操作コスト（回転のオーバーヘッド）を反映している。
4.3 貪欲アルゴリズムとコスト最適化
貪欲アルゴリズムの理論
Richard KarpとDavid Johnsonらによる組合せ最適化の研究（1970年代）は、貪欲アルゴリズム（Greedy Algorithm）の理論的基盤を確立した。
貪欲アルゴリズムの定義（Cormen et al., "Introduction to Algorithms", 1990）:
各ステップで局所的に最適な選択を行い、
全体的な最適解を構築しようとするアルゴリズム
貪欲法が最適解を与える条件:
- 最適部分構造: 問題の最適解が部分問題の最適解を含む
- 貪欲選択性質: 局所最適な選択が大域最適解の一部となる
push_swapでは、これらの条件は厳密には満たされないが、貪欲法は良好な近似解を与える。
Turkishソートの理論的基盤
「Turkishソート」（または「コストベースソート」）は、貪欲アルゴリズムの一種である。各ステップで「最小コストの要素」を選択し、スタックAに挿入する。
コスト関数の定義:
スタックBのi番目の要素をスタックAに挿入するコストを$C(i)$とする:
$$C(i) = C_A(i) + C_B(i) - \min(S_A(i), S_B(i))$$
ここで:
- $C_A(i)$: スタックAでの回転コスト（符号付き）
- $C_B(i)$: スタックBでの回転コスト（符号付き）
- $S_A(i), S_B(i)$: 同期回転可能な回数
同期回転の効果:
- 両方とも正（ra, rb → rr）または負（rra, rrb → rrr）なら、1操作で2回転可能
- 異なる符号なら、個別回転が必要
コスト計算の例:
スタックA: [3, 5, 8, 12, 15] (サイズ5)
スタックB: [7, 10, 2, 14, 6] (サイズ5)
要素7をスタックAに挿入する場合:
- 目標位置: 5と8の間 (位置2)
- C_A = +2 (ra×2)
- C_B = 0 (既にtop)
- 同期なし
- 総コスト = 2 + 0 = 2
要素2をスタックAに挿入する場合:
- 目標位置: 最小値の前 (位置0)
- C_A = 0 または -1 (rra×1でも到達可能)
- C_B = +2 (rb×2) または -3 (rrb×3)
- 最小: C_A=-1, C_B=-3 → 同期可能1回
- 総コスト = |−1| + |−3| − 1 = 3
挿入位置の決定
スタックAの適切な挿入位置を見つけるアルゴリズムは、二分探索の変形である。
ただし、スタックは循環的にソートされている可能性があるため、単純な二分探索は使えない。
循環ソート配列での挿入位置:
/* 循環ソート配列での挿入位置を見つける */
int find_target_position(t_stack *a, int value, int size_a)
{
t_stack *curr;
int pos;
int min_pos;
int max_pos;
int min_val;
int max_val;
// 最小値と最大値の位置を見つける
min_val = INT_MAX;
max_val = INT_MIN;
curr = a;
pos = 0;
while (pos < size_a)
{
if (curr->index < min_val)
{
min_val = curr->index;
min_pos = pos;
}
if (curr->index > max_val)
{
max_val = curr->index;
max_pos = pos;
}
curr = curr->next;
pos++;
}
// 範囲外チェック
if (value < min_val || value > max_val)
return (min_pos);
// 適切な位置を線形探索
curr = a;
pos = 0;
while (pos < size_a)
{
int next_pos = (pos + 1) % size_a;
t_stack *next = get_element_at(a, next_pos);
if (curr->index < value && value < next->index)
return (next_pos);
// 循環境界を跨ぐ場合
if (curr->index > next->index)
{
if (value > curr->index || value < next->index)
return (next_pos);
}
curr = curr->next;
pos++;
}
return (0);
}
4.4 チャンクソートの実装
アルゴリズムの全体像
チャンクソートは以下の3フェーズで構成される:
フェーズ1（分配）: スタックAからスタックBへ、チャンクごとに移動
フェーズ2（逆順挿入）: スタックBから最大値順にスタックAへ戻す
フェーズ3（調整）: スタックAを最終的にソート
フェーズ1: チャンク分配
/* チャンクサイズを計算 */
int calculate_chunk_size(int total_size)
{
/* 経験的に最適化された値 */
if (total_size <= 100)
return (total_size / 5); /* 5チャンク ≈ 20要素/チャンク */
else if (total_size <= 500)
return (total_size / 11); /* 11チャンク ≈ 45要素/チャンク */
else
return ((int)sqrt(total_size * 2)); /* √(2n)に基づく */
}
/* チャンクをスタックBにプッシュ */
void push_chunk_to_b(t_data *data, int min_idx, int max_idx)
{
int pushed;
int median;
pushed = 0;
median = (min_idx + max_idx) / 2;
while (pushed < (max_idx - min_idx) && data->size_a > 0)
{
if (data->a->index >= min_idx && data->a->index < max_idx)
{
pb(data);
pushed++;
/* スタックBの事前整理: 中央値より小さい要素を下に */
if (data->size_b > 1 && data->b->index < median)
rb(data);
}
else
{
ra(data);
}
}
}
事前整理の効果:
プッシュ時にrbを実行することで、スタックBが概ねソートされた状態になる。これにより、フェーズ2での最大値探索が効率化される。
数学的に、事前整理なしの場合、最大値探索に平均$O(n/k)$の回転が必要だが、事前整理ありなら平均$O(n/2k)$に削減できる。
フェーズ2: 最大値の逆順挿入
/* スタックBの最大値をスタックAにプッシュ */
void push_max_to_a(t_data *data)
{
int max_pos;
int cost;
max_pos = find_max_position(data->b, data->size_b);
cost = calculate_rotate_cost(max_pos, data->size_b);
/* 最小コストの方向で回転 */
while (cost > 0)
{
rb(data);
cost--;
}
while (cost < 0)
{
rrb(data);
cost++;
}
pa(data);
}
/* 最大値の位置を見つける */
int find_max_position(t_stack *stack, int size)
{
t_stack *curr;
int max_idx;
int max_pos;
int pos;
curr = stack;
max_idx = INT_MIN;
max_pos = 0;
pos = 0;
while (pos < size)
{
if (curr->index > max_idx)
{
max_idx = curr->index;
max_pos = pos;
}
curr = curr->next;
pos++;
}
return (max_pos);
}
4.5 Turkishソートの実装
コスト構造体
typedef struct s_cost
{
int pos_b; /* スタックBでの位置 */
int cost_a; /* スタックAでの回転コスト（符号付き） */
int cost_b; /* スタックBでの回転コスト（符号付き） */
int total; /* 総コスト（同期回転考慮後） */
} t_cost;
コスト計算
/* 総コストを計算 */
t_cost calculate_total_cost(t_data *data, int b_index)
{
t_cost cost;
int target_pos;
t_stack *elem;
elem = get_element_at(data->b, b_index);
target_pos = find_target_position(data->a, elem->index, data->size_a);
cost.pos_b = b_index;
cost.cost_b = calculate_rotate_cost(b_index, data->size_b);
cost.cost_a = calculate_rotate_cost(target_pos, data->size_a);
/* 同期回転を考慮した総コスト */
if ((cost.cost_a > 0 && cost.cost_b > 0) ||
(cost.cost_a < 0 && cost.cost_b < 0))
{
/* 同じ方向: 大きい方の絶対値 */
int abs_a = abs(cost.cost_a);
int abs_b = abs(cost.cost_b);
cost.total = (abs_a > abs_b) ? abs_a : abs_b;
}
else
{
/* 異なる方向: 両方の絶対値の和 */
cost.total = abs(cost.cost_a) + abs(cost.cost_b);
}
/* pa操作の1を加算 */
cost.total += 1;
return (cost);
}
最小コスト要素の選択と実行
/* 最小コストの要素をスタックAへプッシュ */
void push_cheapest_to_a(t_data *data)
{
t_cost best;
t_cost current;
int i;
/* 最初の要素で初期化 */
best = calculate_total_cost(data, 0);
/* より低コストの要素を探索 */
i = 1;
while (i < data->size_b)
{
current = calculate_total_cost(data, i);
if (current.total < best.total)
best = current;
/* コスト1は最小可能値なので探索終了 */
if (best.total == 1)
break;
i++;
}
/* 最小コストの要素を移動 */
execute_move_optimized(data, best);
}
/* 同期回転を使った最適化移動 */
void execute_move_optimized(t_data *data, t_cost cost)
{
/* 両方とも正の回転 → rr */
while (cost.cost_a > 0 && cost.cost_b > 0)
{
rr(data);
cost.cost_a--;
cost.cost_b--;
}
/* 両方とも負の回転 → rrr */
while (cost.cost_a < 0 && cost.cost_b < 0)
{
rrr(data);
cost.cost_a++;
cost.cost_b++;
}
/* 残りの個別回転 */
while (cost.cost_a > 0)
{
ra(data);
cost.cost_a--;
}
while (cost.cost_a < 0)
{
rra(data);
cost.cost_a++;
}
while (cost.cost_b > 0)
{
rb(data);
cost.cost_b--;
}
while (cost.cost_b < 0)
{
rrb(data);
cost.cost_b++;
}
pa(data);
}
4.6 ハイブリッドアプローチ
戦略選択の理論
異なるアルゴリズムの長所を組み合わせる「ハイブリッドアルゴリズム」は、実用的なソートでは一般的である。
例: Timsort（2002年）
Python言語の標準ソートであるTimsort（Tim Peters作）は、マージソートと挿入ソートのハイブリッドである。小さな部分配列には挿入法を、大きな配列にはマージ法を適用する。
push_swapでも同様のハイブリッド戦略が有効:
/* ハイブリッドソート */
void hybrid_sort(t_data *data)
{
if (data->total_size <= 5)
{
/* 5以下: 専用の最適アルゴリズム */
small_sort(data);
}
else if (data->total_size <= 100)
{
/* 100以下: Turkishソート */
turkish_sort(data);
}
else
{
/* 100超: チャンク + Turkish */
chunk_turkish_sort(data);
}
}
/* Turkishソート（完全版） */
void turkish_sort(t_data *data)
{
/* フェーズ1: 3要素を残してスタックBへ */
while (data->size_a > 3)
pb(data);
/* フェーズ2: 残り3要素をソート */
sort_three(data);
/* フェーズ3: コストベースでスタックAに戻す */
while (data->size_b > 0)
push_cheapest_to_a(data);
/* フェーズ4: 最終調整 */
final_rotation(data);
}
/* チャンク + Turkishハイブリッド */
void chunk_turkish_sort(t_data *data)
{
int chunk_size;
int chunk_num;
int min_idx;
int max_idx;
chunk_size = calculate_chunk_size(data->total_size);
chunk_num = 0;
/* フェーズ1: チャンク分配 */
while (data->size_a > 3)
{
min_idx = chunk_num * chunk_size;
max_idx = min_idx + chunk_size;
if (max_idx > data->total_size)
max_idx = data->total_size;
push_chunk_to_b(data, min_idx, max_idx);
chunk_num++;
}
/* フェーズ2: 残り3要素をソート */
sort_three(data);
/* フェーズ3: コストベースで戻す */
while (data->size_b > 0)
push_cheapest_to_a(data);
/* フェーズ4: 最終調整 */
final_rotation(data);
}
4.7 最終調整と検証
循環ソートの調整
/* スタックAを最終的にソートされた状態にする */
void final_rotation(t_data *data)
{
int min_pos;
int cost;
if (is_sorted(data->a))
return;
/* 最小値の位置を見つける */
min_pos = find_min_position(data->a, data->size_a);
/* 最小値をtopに移動 */
cost = calculate_rotate_cost(min_pos, data->size_a);
while (cost > 0)
{
ra(data);
cost--;
}
while (cost < 0)
{
rra(data);
cost++;
}
}
/* ソート完了チェック */
int is_sorted(t_stack *stack)
{
t_stack *curr;
if (!stack)
return (1);
curr = stack;
while (curr->next)
{
if (curr->index > curr->next->index)
return (0);
curr = curr->next;
}
return (1);
}
4.8 パフォーマンス目標
評価基準
42の評価基準は以下の通り:
100要素:
- 5点: 700操作以下
- 4点: 900操作以下
- 3点: 1100操作以下
- 2点: 1300操作以下
- 1点: 1500操作以下
500要素:
- 5点: 5500操作以下
- 4点: 7000操作以下
- 3点: 8500操作以下
- 2点: 10000操作以下
- 1点: 11500操作以下
理論的下限との比較
比較ソートの下限は$\Omega(n \log n)$だが、push_swapでは各比較に複数の操作が必要である。
100要素の場合:
- 理論的下限: $\lceil \log_2(100!) \rceil = 525$回の比較
- 実用的下限: 各要素に平均6-7操作 → 約600-700操作
- 目標（5点）: 700操作
500要素の場合:
- 理論的下限: $\lceil \log_2(500!) \rceil = 3,767$回の比較
- 実用的下限: 各要素に平均10-11操作 → 約5000-5500操作
- 目標（5点）: 5500操作
- 分割統治法の歴史: von Neumannのマージソート、Hoareのクイックソート
- バケットソート理論: Sewardの分布ソート、チャンク数の最適化
- 貪欲アルゴリズム: コスト関数の設計、Turkishソートの理論
- ハイブリッド戦略: サイズに応じた戦略選択
- 実装技法: 同期回転の活用、循環配列での挿入位置決定
- von Neumann, J. (1945). "First Draft of a Report on the EDVAC"
- Hoare, C. A. R. (1962). "Quicksort", Computer Journal, 5(1), pp. 10-16
- Knuth, D. E. (1973). "The Art of Computer Programming, Vol. 3: Sorting and Searching"
- Seward, H. H. (1954). "Information sorting in the application of electronic digital computers to business operations", MIT Master's Thesis
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (1990). "Introduction to Algorithms", MIT Press
- Peters, T. (2002). "Timsort description", Python Enhancement Proposals
4.9 まとめ
本章では、大規模データのソートに必要な理論と実装を学んだ:
次章では、基数ソート（Radix Sort）という、比較を行わないソートアルゴリズムとそのpush_swapへの応用を学ぶ。
---