ソートアルゴリズムの歴史と計算量理論：スタックデータ構造の基礎
ソートの歴史：人類最古のアルゴリズム問題
古代からの順序付けへの探求
人類が「順序」という概念を扱い始めた歴史は、文明の始まりと同じくらい古い。紀元前2000年頃のバビロニアの粘土板には、数値を順序付けるための手法が記録されている。古代エジプトの書記官たちは、パピルスに記録された情報を効率的に検索するために、アルファベット順の索引を作成した。
しかし、アルゴリズム（algorithm）という言葉自体は、9世紀のペルシャの数学者Muhammad ibn Musa al-Khwarizmiの名前に由来する。彼の著作「Kitab al-Jabr」は代数学の基礎を築き、その名前のラテン語化「Algoritmi」が、体系的な計算手順を意味する用語となった。
機械式ソートの黎明：Herman Hollerith
ソートの機械化は、1890年のアメリカ国勢調査から始まる。Herman Hollerith（1860-1929）は、パンチカードを使用したタビュレーティングマシンを発明し、調査データの集計時間を数年から数週間に短縮した。
Hollerithのパンチカードシステム (1890):
┌────────────────────────────────────┐
│ ● ○ ○ ● ○ ● ○ ○ ● ○ ● ○ │ パンチカード
│ ○ ● ○ ○ ● ○ ● ● ○ ● ○ ● │ （穴の有無でデータを表現）
└────────────────────────────────────┘
↓
ソーティングマシン
↓
カードの物理的な分類
特徴:
- 基数ソートの機械的実装
- 各桁の穴の位置でカードを分類
- O(d × n) の時間計算量（d = 桁数）
Hollerithの会社は後に、IBMの前身となる。彼のソーティングマシンは、現代の基数ソート（Radix Sort）の原型であり、Push_swapプロジェクトで使用される技法の歴史的起源でもある。
電子計算機時代のソート：ENIAC以降
1945年、世界初の汎用電子計算機ENIACが稼働を開始した。しかし、ソートアルゴリズムの科学的研究は、1945年のJohn von Neumannによるマージソートの考案から本格的に始まる。von Neumannは、EDVACプロジェクトの一環として、ソートの分割統治法を提案した。
1959年、Donald Shellは、挿入ソートの改良版であるシェルソートを発表。これは、離れた要素間の比較を可能にすることで、挿入ソートの弱点を克服した最初のアルゴリズムの一つである。
1962年、Tony Hoareはクイックソートを発表した（Communications of the ACM）。この分割統治アルゴリズムは、平均的なケースでO(n log n)の時間計算量を達成し、実用上最も高速なソートアルゴリズムの一つとなった。
ソートアルゴリズムの歴史年表:
1890 Herman Hollerith 基数ソートの機械的実装
1945 John von Neumann マージソート
1959 Donald Shell シェルソート
1962 Tony Hoare クイックソート
1964 Robert Floyd ヒープソート（Williams との共同）
1969 Robert Sedgewick クイックソートの改良解析
1993 Jon Bentley イントロソート
2002 Tim Peters Timsort（Python標準）
---
スタックデータ構造の歴史と理論
スタックの発明：Alan TuringからCharles Hamblinへ
スタック（Stack）の概念は、1946年のAlan Turingの論文「Proposed Electronic Calculator」に最初の形態が見られる。Turingは、サブルーチン呼び出しの戻りアドレスを保存するために「buried」アドレスという概念を使用した。
しかし、スタックを明示的なデータ構造として定式化したのは、1957年のFriedrich L. BauerとKlaus Samelsonである。彼らはミュンヘン工科大学で、式の評価とサブルーチン呼び出しのために「Keller」（ドイツ語で「地下室」）と呼ばれるLIFO構造を開発した。
1957年、オーストラリアの論理学者Charles Hamblinは、論文「An Addressless Coding Scheme based on Mathematical Notation」で、逆ポーランド記法（Reverse Polish Notation, RPN）とスタックベースの計算機アーキテクチャを提案した。この研究は、後のHP電卓やPostScript言語に影響を与えた。
スタックの歴史的発展:
1946 Alan Turing 「buried」アドレスの概念
1957 Bauer & Samelson 「Keller」（スタック）の定式化
1957 Charles Hamblin 逆ポーランド記法とスタック計算機
1960 John McCarthy LISP言語（スタックベースの関数呼び出し）
1963 Edsger Dijkstra Shunting-yard アルゴリズム
1972 HP-35 電卓 初のスタックベース計算機の商業化
LIFOの公理的定義
スタックは、以下の公理によって形式的に定義される。これは、抽象データ型（ADT）としてのスタックの数学的特性を表現している：
スタックの公理的定義 (Algebraic Specification):
signature Stack[T]:
new : → Stack[T]
push : Stack[T] × T → Stack[T]
pop : Stack[T] → Stack[T] × T
top : Stack[T] → T
empty : Stack[T] → Boolean
axioms:
(1) empty(new()) = true
(2) empty(push(s, x)) = false
(3) top(push(s, x)) = x
(4) pop(push(s, x)) = (s, x)
(5) pop(new()) = error
不変条件:
∀ s ∈ Stack, x ∈ T:
pop(push(s, x)) = s (LIFO原則)
この公理系は、1974年のJohn Guttag（MITの計算機科学者）による抽象データ型の形式仕様に基づく。
C言語によるスタック実装
連結リストを使用したスタック実装は、ポインタ操作の理解に最適な教材である：
/*
** スタックノード：von Neumannのメモリモデルに基づく
** 各ノードはデータとポインタで構成
*/
typedef struct s_stack
{
int value; /* 格納される値 */
int index; /* 正規化されたインデックス */
struct s_stack *next; /* 次のノードへのポインタ */
} t_stack;
/*
** Push操作：O(1)時間計算量
** Bauer & Samelson (1957) の定式化に基づく
*/
t_stack *stack_push(t_stack *stack, int value)
{
t_stack *new_node;
new_node = malloc(sizeof(t_stack));
if (!new_node)
return (NULL);
new_node->value = value;
new_node->index = -1;
new_node->next = stack;
return (new_node);
}
/*
** Pop操作：O(1)時間計算量
** 公理 (4): pop(push(s, x)) = (s, x)
*/
t_stack *stack_pop(t_stack *stack, int *value)
{
t_stack *next;
if (!stack)
return (NULL);
if (value)
*value = stack->value;
next = stack->next;
free(stack);
return (next);
}
/*
** Top操作：O(1)時間計算量
** 公理 (3): top(push(s, x)) = x
*/
int stack_top(t_stack *stack)
{
if (!stack)
return (0); /* エラー：空スタック */
return (stack->value);
}
/*
** Empty判定：O(1)時間計算量
** 公理 (1), (2) に基づく
*/
int stack_empty(t_stack *stack)
{
return (stack == NULL);
}
/*
** Size計算：O(n)時間計算量
** 最適化：サイズをメタデータとして保持可能
*/
int stack_size(t_stack *stack)
{
int count;
count = 0;
while (stack)
{
count++;
stack = stack->next;
}
return (count);
}
---
計算量理論の基礎
Alan TuringとChurch-Turing Thesis
計算量理論（Computational Complexity Theory）の起源は、1936年のAlan Turingの論文「On Computable Numbers, with an Application to the Entscheidungsproblem」に遡る。Turingは、チューリングマシンという抽象的な計算モデルを導入し、計算可能性の形式的定義を与えた。
同年、Alonzo Churchはラムダ計算を提案し、計算可能関数の別の定義を与えた。これら二つの定式化が同値であることから、Church-Turing Thesisが確立された：
> 「直感的に計算可能な関数は、すべてチューリングマシンで計算可能である」
Big O記法の歴史：Edmund Landauから Donald Knuthへ
Big O記法は、1894年のドイツの数学者Paul Bachmannの著作「Die Analytische Zahlentheorie」で初めて使用された。しかし、この記法を広めたのはEdmund Landauであり、彼の名前から「Landau記法」とも呼ばれる。
コンピュータ科学への応用は、1965年のDonald Knuthによる。Knuthは、著作「The Art of Computer Programming」（1968年開始）で、アルゴリズム解析にBig O記法を体系的に導入し、漸近解析（Asymptotic Analysis）をアルゴリズム研究の標準ツールとした。
漸近記法の定義 (Knuth, 1976):
Big O（上界）:
f(n) = O(g(n)) ⟺ ∃ c > 0, n₀ : ∀ n ≥ n₀, |f(n)| ≤ c|g(n)|
Big Ω（下界）:
f(n) = Ω(g(n)) ⟺ ∃ c > 0, n₀ : ∀ n ≥ n₀, f(n) ≥ c · g(n)
Big Θ（タイト境界）:
f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) かつ f(n) = Ω(g(n))
計算量クラスの階層:
O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(n³) ⊂ O(2ⁿ) ⊂ O(n!)
ソートの情報理論的下界
比較ベースのソートアルゴリズムには、情報理論的な下界が存在する。これは1955年のHenry Ricardo Hartleyの情報理論と、1948年のClaude Shannonの通信理論に基づく。
n個の異なる要素のソートにおいて：
- 可能な順列の総数は n! 通り
- 正しい順序を特定するには、少なくとも log₂(n!) 回の比較が必要
- Stirlingの近似により、log₂(n!) ≈ n log₂ n - n log₂ e
比較ソートの下界定理 (Ford & Johnson, 1959):
定理: 任意の比較ベースのソートアルゴリズムは、
最悪の場合 Ω(n log n) 回の比較を必要とする
証明の概略:
1. n個の要素には n! 通りの順列がある
2. 各比較は、可能な順列集合を最大で半分に分割
3. k回の比較で区別できる順列は高々 2^k 通り
4. 2^k ≥ n! より、k ≥ log₂(n!)
5. Stirlingの近似: log₂(n!) ≈ n log₂ n
∴ k = Ω(n log n) □
この下界は、クイックソート、マージソート、ヒープソートなどのO(n log n)アルゴリズムが、比較ベースのソートとして漸近的に最適であることを示している。
---
Push_swapプロジェクトの理論的基盤
問題の形式的定義
Push_swapプロジェクトは、以下のように形式化できる：
Push_swap問題の形式的定義:
入力:
- n個の異なる整数の列 A = (a₁, a₂, ..., aₙ)
- 空の補助スタック B
出力:
- Aを昇順にソートする操作列 S = (s₁, s₂, ..., sₘ)
- Bが空の状態で終了
制約:
- 許可される操作は11種類のみ
- 操作回数 m を最小化
最適化問題:
minimize |S|
subject to:
- S を適用した結果、Aが昇順
- S を適用した結果、Bが空
- 各 sᵢ ∈ {sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr}
42スクールの評価基準
プロジェクトの評価基準は、アルゴリズムの効率性を数値化する：
| 要素数 | 優秀 | 良好 | 合格ライン | 理論的下界 | |--------|------|------|------------|------------| | 3 | 2-3 | - | - | 2 | | 5 | ≤12 | - | - | 7 | | 100 | ≤700 | ≤900 | ≤1100 | ~525 | | 500 | ≤5500 | ≤7000 | ≤8500 | ~4000 |
理論的下界は log₂(n!) に基づくが、Push_swapの制限された操作セットでは、これより多くの操作が必要になる。
許可された11操作の形式的定義
Push_swapで許可される操作を、数学的に定義する：
操作の形式的定義（A, Bは有限列）:
スワップ操作:
sa: (a₁, a₂, ..., aₙ) → (a₂, a₁, ..., aₙ) if n ≥ 2
sb: (b₁, b₂, ..., bₘ) → (b₂, b₁, ..., bₘ) if m ≥ 2
ss: sa と sb を同時実行
プッシュ操作:
pa: (A, b₁:B) → (b₁:A, B) if |B| ≥ 1
pb: (a₁:A, B) → (A, a₁:B) if |A| ≥ 1
ローテーション操作:
ra: (a₁, a₂, ..., aₙ) → (a₂, ..., aₙ, a₁) if n ≥ 1
rb: (b₁, b₂, ..., bₘ) → (b₂, ..., bₘ, b₁) if m ≥ 1
rr: ra と rb を同時実行
逆ローテーション操作:
rra: (a₁, ..., aₙ₋₁, aₙ) → (aₙ, a₁, ..., aₙ₋₁) if n ≥ 1
rrb: (b₁, ..., bₘ₋₁, bₘ) → (bₘ, b₁, ..., bₘ₋₁) if m ≥ 1
rrr: rra と rrb を同時実行
記法: a₁:A は、リスト A の先頭に a₁ を追加した列を表す
---
C言語による基本実装
スワップ操作
/*
** sa (swap a): スタックAの最上部2要素を交換
** 時間計算量: O(1)
** 空間計算量: O(1)
*/
void sa(t_stack **a, int print)
{
t_stack *first;
t_stack *second;
if (!*a || !(*a)->next)
return ;
first = *a;
second = (*a)->next;
first->next = second->next;
second->next = first;
*a = second;
if (print)
write(1, "sa\n", 3);
}
/*
** sb (swap b): スタックBの最上部2要素を交換
*/
void sb(t_stack **b, int print)
{
t_stack *first;
t_stack *second;
if (!*b || !(*b)->next)
return ;
first = *b;
second = (*b)->next;
first->next = second->next;
second->next = first;
*b = second;
if (print)
write(1, "sb\n", 3);
}
/*
** ss: sa と sb を同時実行
*/
void ss(t_stack **a, t_stack **b, int print)
{
sa(a, 0);
sb(b, 0);
if (print)
write(1, "ss\n", 3);
}
プッシュ操作
/*
** pa (push a): スタックBの先頭をスタックAの先頭に移動
** 時間計算量: O(1)
*/
void pa(t_stack **a, t_stack **b, int print)
{
t_stack *moved;
if (!*b)
return ;
moved = *b;
*b = (*b)->next;
moved->next = *a;
*a = moved;
if (print)
write(1, "pa\n", 3);
}
/*
** pb (push b): スタックAの先頭をスタックBの先頭に移動
*/
void pb(t_stack **a, t_stack **b, int print)
{
t_stack *moved;
if (!*a)
return ;
moved = *a;
*a = (*a)->next;
moved->next = *b;
*b = moved;
if (print)
write(1, "pb\n", 3);
}
ローテーション操作
/*
** ra (rotate a): 先頭要素を末尾に移動
** 時間計算量: O(n) - 末尾へのアクセスが必要
*/
void ra(t_stack **a, int print)
{
t_stack *first;
t_stack *last;
if (!*a || !(*a)->next)
return ;
first = *a;
last = *a;
while (last->next)
last = last->next;
*a = first->next;
last->next = first;
first->next = NULL;
if (print)
write(1, "ra\n", 3);
}
/*
** rra (reverse rotate a): 末尾要素を先頭に移動
** 時間計算量: O(n) - 末尾とその前へのアクセスが必要
*/
void rra(t_stack **a, int print)
{
t_stack *last;
t_stack *second_last;
if (!*a || !(*a)->next)
return ;
last = *a;
second_last = NULL;
while (last->next)
{
second_last = last;
last = last->next;
}
second_last->next = NULL;
last->next = *a;
*a = last;
if (print)
write(1, "rra\n", 4);
}
/*
** rb, rrb, rr, rrr は同様の実装（省略）
*/
---
入力処理とエラーハンドリング
引数の検証
堅牢なプログラムには、入力の完全な検証が必要である：
/*
** 文字列が有効な整数かを判定
** 許容形式: [+-]?[0-9]+
*/
int is_valid_integer(const char *str)
{
int i;
i = 0;
if (str[i] == '-' || str[i] == '+')
i++;
if (!str[i])
return (0);
while (str[i])
{
if (str[i] < '0' || str[i] > '9')
return (0);
i++;
}
return (1);
}
/*
** 安全な文字列→長整数変換
** オーバーフロー検出付き
*/
long ft_atol_safe(const char *str, int *error)
{
long result;
int sign;
int i;
result = 0;
sign = 1;
i = 0;
*error = 0;
if (str[i] == '-' || str[i] == '+')
{
if (str[i++] == '-')
sign = -1;
}
while (str[i])
{
/* オーバーフロー検出 */
if (result > (LONG_MAX - (str[i] - '0')) / 10)
{
*error = 1;
return (0);
}
result = result * 10 + (str[i++] - '0');
}
return (result * sign);
}
/*
** INT範囲チェック
*/
int is_in_int_range(long value)
{
return (value >= INT_MIN && value <= INT_MAX);
}
重複検出
O(n²)のナイーブなアルゴリズム、またはO(n log n)のソート+線形スキャン：
/*
** 重複検出: O(n²) ナイーブアルゴリズム
** 小規模入力では許容可能
*/
int has_duplicate_naive(int *arr, int size)
{
int i;
int j;
i = 0;
while (i < size)
{
j = i + 1;
while (j < size)
{
if (arr[i] == arr[j])
return (1);
j++;
}
i++;
}
return (0);
}
/*
** 重複検出: O(n log n) ソートベース
** 大規模入力ではより効率的
*/
int has_duplicate_sorted(int *arr, int size)
{
int *sorted;
int i;
int has_dup;
sorted = malloc(sizeof(int) * size);
if (!sorted)
return (-1); /* エラー */
ft_memcpy(sorted, arr, sizeof(int) * size);
quicksort(sorted, 0, size - 1);
has_dup = 0;
i = 0;
while (i < size - 1 && !has_dup)
{
if (sorted[i] == sorted[i + 1])
has_dup = 1;
i++;
}
free(sorted);
return (has_dup);
}
インデックス正規化
実際の値ではなく、相対的な順位（0からn-1）に変換する。これにより、ビット演算ベースのアルゴリズムが適用可能になる：
/*
** インデックス正規化: 値を順位に変換
** 例: [42, 1, 365, -7, 100] → [2, 1, 4, 0, 3]
**
** 時間計算量: O(n²) - 各要素に対して全要素を走査
** 最適化: ソート+二分探索で O(n log n) も可能
*/
void normalize_indices(t_stack *stack, int size)
{
t_stack *current;
t_stack *compare;
int rank;
current = stack;
while (current)
{
rank = 0;
compare = stack;
while (compare)
{
if (compare->value < current->value)
rank++;
compare = compare->next;
}
current->index = rank;
current = current->next;
}
}
/*
** 正規化の意義:
**
** 1. 値の範囲を [0, n-1] に制限
** → ビット演算（基数ソート）が適用可能
**
** 2. 相対的な大小関係のみを保存
** → 絶対値は不要
**
** 3. メモリ効率の向上
** → 値を格納する必要がなくなる（インデックスのみで十分）
*/
---
ソート済み判定と基本ユーティリティ
/*
** スタックがソート済みかを判定
** 時間計算量: O(n)
*/
int is_sorted(t_stack *stack)
{
if (!stack)
return (1);
while (stack->next)
{
if (stack->value > stack->next->value)
return (0);
stack = stack->next;
}
return (1);
}
/*
** スタックの最小値のインデックス位置を取得
*/
int find_min_position(t_stack *stack)
{
int min_val;
int min_pos;
int pos;
if (!stack)
return (-1);
min_val = stack->value;
min_pos = 0;
pos = 0;
while (stack)
{
if (stack->value < min_val)
{
min_val = stack->value;
min_pos = pos;
}
pos++;
stack = stack->next;
}
return (min_pos);
}
/*
** スタックの最大値のインデックス位置を取得
*/
int find_max_position(t_stack *stack)
{
int max_val;
int max_pos;
int pos;
if (!stack)
return (-1);
max_val = stack->value;
max_pos = 0;
pos = 0;
while (stack)
{
if (stack->value > max_val)
{
max_val = stack->value;
max_pos = pos;
}
pos++;
stack = stack->next;
}
return (max_pos);
}
---
まとめ：歴史的基盤から実装へ
この章では、Push_swapプロジェクトの理論的基盤を学んだ：
ソートアルゴリズムの歴史
- Herman Hollerith (1890): 機械式ソートの発明、基数ソートの原型
- John von Neumann (1945): マージソートの考案
- Tony Hoare (1962): クイックソートの発表
スタックデータ構造
- Alan Turing (1946): サブルーチン呼び出しでの原型
- Bauer & Samelson (1957): 「Keller」としての形式化
- Charles Hamblin (1957): 逆ポーランド記法とスタック計算機
計算量理論
- Paul Bachmann (1894): Big O記法の導入
- Donald Knuth (1968〜): アルゴリズム解析への体系的応用
- Ford & Johnson (1959): 比較ソートの下界 Ω(n log n)
Push_swapへの応用
- 11の許可された操作の形式的定義
- スタックのC言語実装
- 入力検証とインデックス正規化
次章では、これらの操作を組み合わせて、小規模入力（3〜5要素）の効率的なソートアルゴリズムを設計する。