4-5. ソートアルゴリズムと計算量

このセクションで学ぶこと

• Big O 記法でアルゴリズムの計算量を評価する方法を理解する
• バブルソート・選択ソート・クイックソートの仕組みと計算量の違いを学ぶ
• フィボナッチ数列を題材に、素朴な再帰・メモ化・反復の性能差を体感する
• 「動くコード」と「速いコード」の違いを計算量の観点から理解する

ソートアルゴリズムとは

ソートとは、データを一定の順序（昇順・降順など）に並べ替える処理である。 日常的な操作（検索、ランキング表示、最小値・最大値取得）の多くはソート済みデータを前提としているため、ソートアルゴリズムの理解は実務の基礎となる。

アルゴリズムを選ぶ際に重要なのは計算量（時間複雑度）である。 同じ結果を出すアルゴリズムでも、データ量が増えたときの速度が大きく変わる。

---

Big O 記法

計算量は Big O 記法 で表す。O(f(n)) は「データ量 n が増えたとき、処理時間がおよそ f(n) の割合で増える」という意味である。

     n =     10      100    1,000
O(1)           1        1        1   ← どんなに増えても一定
O(log n)       3        7       10   ← 2倍に増えてもほぼ1ステップ増えるだけ
O(n)          10      100    1,000   ← データに比例
O(n log n)    33      664    9,966   ← 実用ソートの目安
O(n²)        100   10,000  1,000,000 ← データが10倍で100倍遅くなる
O(2ⁿ)      1,024    ≈10³⁰   ≈10³⁰¹  ← 指数的爆発・実用不可

「O(n²) と O(n log n) の違いは小さい」と感じるかもしれないが、n=1,000 で約100倍、n=10,000 で約1,000倍の差になる。

---

バブルソート — O(n²)

隣り合う2要素を比較し、逆順なら交換する。これを繰り返すと、最大値が毎回末尾へ「浮かんで」くる。

データ: [5, 3, 8, 1, 2]

──── パス 1（最大値 8 を末尾へ確定）────
比較: (5)[3] 8  1  2  → swap  →  3  5  8  1  2
比較:  3 (5)[8] 1  2  → keep  →  3  5  8  1  2
比較:  3  5 (8)[1] 2  → swap  →  3  5  1  8  2
比較:  3  5  1 (8)[2] → swap  →  3  5  1  2  8 ✓

──── パス 2（次大値 5 を確定）────
比較: (3)[5] 1  2  8  → keep
比較:  3 (5)[1] 2  8  → swap  →  3  1  5  2  8
比較:  3  1 (5)[2] 8  → swap  →  3  1  2  5  8 ✓

──── パス 3・4 ────（省略）
結果: [1, 2, 3, 5, 8]

n 要素に対して最大 n×(n-1)/2 回の比較が発生するため、計算量は O(n²) となる。 シンプルで実装しやすいが、n が大きいと遅い。

function bubbleSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]]; // 交換
      }
    }
  }
  return a;
}

---

選択ソート — O(n²)

未整列部分から最小値を選んで先頭に置く。バブルソートと同じ O(n²) だが、交換回数が少ないのが特徴である。

データ: [5, 3, 8, 1, 2]

パス 1: 未整列 [5,3,8,1,2] の最小 = 1 → [1] と [5] を交換 → [1, 3, 8, 5, 2]
パス 2: 未整列 [3,8,5,2] の最小 = 2  → [2] と [3] を交換 → [1, 2, 8, 5, 3]
パス 3: 未整列 [8,5,3] の最小 = 3   → [3] と [8] を交換 → [1, 2, 3, 5, 8]
パス 4: 未整列 [5,8] の最小 = 5     → そのまま           → [1, 2, 3, 5, 8] ✓

function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
  return a;
}

---

クイックソート — 平均 O(n log n)

「pivot（基準値）」を選び、それより小さい要素を左、大きい要素を右に分けて再帰的に整列する。 平均計算量は O(n log n) で、実用上最も高速なソートのひとつである。

データ: [5, 3, 8, 1, 2]  pivot = 5（先頭）

分割: 左[3, 1, 2]  pivot[5]  右[8]
        ↓ 再帰              ↓ 再帰
  pivot=3: 左[1,2] pivot[3] 右[]   右[8]はそのまま
        ↓ 再帰
  pivot=1: 左[]  pivot[1] 右[2]

結合: [1, 2] + [3] + [5] + [8] = [1, 2, 3, 5, 8]

分割のたびにデータが半分に近い大きさになる
→ 再帰の深さ ≈ log₂(n)
→ 各深さで合計 n 回の比較
→ 合計 ≈ n × log(n) 回

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left  = arr.slice(1).filter(x => x <= pivot);
  const right = arr.slice(1).filter(x => x >  pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

---

ソートアルゴリズム比較

アルゴリズム	平均計算量	最悪計算量	安定性	特徴
バブルソート	O(n²)	O(n²)	安定	最もシンプル
選択ソート	O(n²)	O(n²)	不安定	交換回数が少ない
挿入ソート	O(n²)	O(n²)	安定	ほぼ整列済みなら速い
クイックソート	O(n log n)	O(n²)	不安定	実用上最速のひとつ
マージソート	O(n log n)	O(n log n)	安定	最悪でも安定して速い

「安定」とは、同じ値の要素の順序が整列後も保たれることを意味する。

---

フィボナッチ数列と計算量

フィボナッチ数列（0, 1, 1, 2, 3, 5, 8, 13, …）は再帰の入門例としてよく使われるが、 実装方法によって計算量が劇的に変わるため、計算量の理解にも最適な題材である。

素朴な再帰 — O(2ⁿ)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // 2回再帰呼び出し
}

fib(n) を呼ぶと fib(n-1) と fib(n-2) が呼ばれ、それぞれがさらに2回呼ばれる。 呼び出し回数はおよそ 2ⁿ 回に爆発する。

fib(5) の呼び出しツリー

                fib(5)
              ↙        ↘
          fib(4)       fib(3)
          ↙    ↘       ↙    ↘
       fib(3) fib(2) fib(2) fib(1)
       ↙   ↘   ↙  ↘   ↙  ↘
    fib(2) fib(1) ...

fib(3) が 2回、fib(2) が 3回、同じ計算が繰り返されている
n=40 では約 2億回の呼び出しが発生する

メモ化再帰 — O(n)

計算済みの結果を Map に保存し、2度目以降は即座に返す。

function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n); // キャッシュから即返却
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

各 fib(k) は1回しか計算されないため、合計計算量は O(n) になる。

反復処理 — O(n)

ループで順番に計算する。再帰のオーバーヘッドがなく、最も効率的である。

function fibIter(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

性能比較（目安）

手法	fib(20)	fib(35)	fib(45)
素朴な再帰	< 1ms	~数十ms	~数秒
メモ化	< 1ms	< 1ms	< 1ms
反復	< 1ms	< 1ms	< 1ms

n=45 前後で素朴な再帰は数秒〜十数秒かかる一方、メモ化と反復は変わらずほぼ瞬時に返る。 同じ「正しい答え」でも、アルゴリズムの違いで実用性が天と地ほど変わる。

---

まとめ

概念	要点
Big O 記法	アルゴリズムの計算量をデータ量 n の関数で表す
バブルソート	O(n²)。実装シンプル。大きなデータには不向き
クイックソート	平均 O(n log n)。実用的な速さ
素朴な再帰 fib	O(2ⁿ)。n が増えると指数的に遅くなる
メモ化・反復 fib	O(n)。計算済みを再利用することで劇的に高速化

「動く」コードと「速い」コードは別物である。 小さなデータでは差が見えないが、n が大きくなったときに計算量の選択が生死を分ける。

次のステップ

• 4-5. 演習問題
• 第4章を終えたら、5-1. RDB・テーブル設計・正規化 へ進もう。