10日で覚えるData Structure & AlgorithmDay 6: ソートアルゴリズム
books.chapter 610日で覚えるData Structure & Algorithm

Day 6: ソートアルゴリズム

今日学ぶこと

  • 基本的なソート：バブルソート、選択ソート、挿入ソート
  • 効率的なソート：マージソート、クイックソート
  • 各ソートの特徴と使い分け
  • JavaScriptの組み込みソート

ソートアルゴリズムの分類

flowchart TB
    subgraph Basic["基本ソート O(n²)"]
        BS["バブルソート"]
        SS["選択ソート"]
        IS["挿入ソート"]
    end
    subgraph Efficient["効率的ソート O(n log n)"]
        MS["マージソート"]
        QS["クイックソート"]
    end
    style Basic fill:#f59e0b,color:#fff
    style Efficient fill:#22c55e,color:#fff

バブルソート（Bubble Sort）

隣接する要素を比較して交換を繰り返します。最大値が泡のように浮かび上がります。

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // Already sorted
  }
  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]
特性 値
最良 O(n) ※既にソート済み
平均 O(n²)
最悪 O(n²)
空間 O(1)
安定 Yes

選択ソート（Selection Sort）

未ソート部分から最小値を見つけ、先頭に配置します。

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}
特性 値
最良 O(n²)
平均 O(n²)
最悪 O(n²)
空間 O(1)
安定 No

挿入ソート（Insertion Sort）

手持ちのカードをソートするように、各要素を正しい位置に挿入します。

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}
特性 値
最良 O(n) ※既にソート済み
平均 O(n²)
最悪 O(n²)
空間 O(1)
安定 Yes

挿入ソートは小さな配列やほぼソート済みのデータに対して非常に効率的です。

マージソート（Merge Sort）

分割統治法を使い、配列を半分に分割→ソート→マージします。

flowchart TB
    A["[38, 27, 43, 3]"] --> B["[38, 27]"]
    A --> C["[43, 3]"]
    B --> D["[38]"]
    B --> E["[27]"]
    C --> F["[43]"]
    C --> G["[3]"]
    D -.-> H["[27, 38]"]
    E -.-> H
    F -.-> I["[3, 43]"]
    G -.-> I
    H -.-> J["[3, 27, 38, 43]"]
    I -.-> J
    style A fill:#3b82f6,color:#fff
    style J fill:#22c55e,color:#fff

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}
特性 値
最良 O(n log n)
平均 O(n log n)
最悪 O(n log n)
空間 O(n)
安定 Yes

クイックソート（Quick Sort）

ピボットを選び、小さい要素を左、大きい要素を右に分割します。

flowchart TB
    A["[8, 3, 1, 7, 0, 10, 2]"] --> P["ピボット: 7"]
    P --> L["左: [3, 1, 0, 2]"]
    P --> R["右: [8, 10]"]
    L --> L2["[0, 1, 2, 3]"]
    R --> R2["[8, 10]"]
    L2 --> RESULT["[0, 1, 2, 3, 7, 8, 10]"]
    R2 --> RESULT
    style P fill:#f59e0b,color:#fff
    style L fill:#3b82f6,color:#fff
    style R fill:#ef4444,color:#fff
    style RESULT fill:#22c55e,color:#fff

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([8, 3, 1, 7, 0, 10, 2]));
// [0, 1, 2, 3, 7, 8, 10]

インプレース版クイックソート

function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSortInPlace(arr, low, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}
特性 値
最良 O(n log n)
平均 O(n log n)
最悪 O(n²) ※既にソート済みでピボットが端
空間 O(log n)
安定 No

ソートアルゴリズムの比較

アルゴリズム 最良 平均 最悪 空間 安定
バブルソート O(n) O(n²) O(n²) O(1) Yes
選択ソート O(n²) O(n²) O(n²) O(1) No
挿入ソート O(n) O(n²) O(n²) O(1) Yes
マージソート O(n log n) O(n log n) O(n log n) O(n) Yes
クイックソート O(n log n) O(n log n) O(n²) O(log n) No

安定ソートとは

安定ソートは、同じ値の要素の相対的な順序を保持します。

const students = [
  { name: "Alice", grade: "B" },
  { name: "Bob", grade: "A" },
  { name: "Charlie", grade: "B" },
  { name: "Diana", grade: "A" },
];

// Stable sort by grade preserves original order within same grade:
// A: Bob, Diana (original order preserved)
// B: Alice, Charlie (original order preserved)

JavaScriptの Array.sort()

// Default: converts to strings and sorts lexicographically
[10, 9, 8, 1, 2, 3].sort();
// [1, 10, 2, 3, 8, 9] — NOT numerical order!

// Numerical sort with comparator
[10, 9, 8, 1, 2, 3].sort((a, b) => a - b);
// [1, 2, 3, 8, 9, 10]

// Sort objects
const people = [
  { name: "Charlie", age: 30 },
  { name: "Alice", age: 25 },
  { name: "Bob", age: 35 },
];
people.sort((a, b) => a.age - b.age);
// [{ Alice, 25 }, { Charlie, 30 }, { Bob, 35 }]

JavaScriptのArray.sort()は安定ソートが保証されています（ECMAScript 2019以降）。内部実装はTimSort（マージソート + 挿入ソートのハイブリッド）を使うことが多いです。

どのソートを使うべきか

flowchart TB
    Q1{"データ量は？"}
    Q1 -->|"少ない（< 50）"| IS["挿入ソート"]
    Q1 -->|"多い"| Q2{"メモリ制約は？"}
    Q2 -->|"制約あり"| QS["クイックソート"]
    Q2 -->|"制約なし"| Q3{"安定性が必要？"}
    Q3 -->|"Yes"| MS["マージソート"]
    Q3 -->|"No"| QS
    style IS fill:#22c55e,color:#fff
    style QS fill:#3b82f6,color:#fff
    style MS fill:#8b5cf6,color:#fff

まとめ

概念 説明
バブルソート 隣接要素を交換、教育用途
選択ソート 最小値を選択して配置
挿入ソート 小さいデータに効率的
マージソート 安定で常にO(n log n)
クイックソート 実践で最も高速、空間効率も良い

重要ポイント

  1. 小さなデータには挿入ソートが実用的
  2. マージソートは安定で常にO(n log n)だがO(n)の追加空間が必要
  3. クイックソートは平均最速だが最悪ケースはO(n²)
  4. JavaScriptのArray.sort()は安定ソート

練習問題

問題1: 基本

与えられた配列を、偶数が前、奇数が後ろになるようにソートしてください（各グループ内の順序は問わない）。

問題2: 応用

文字列の配列を、文字列の長さでソートしてください。同じ長さの場合はアルファベット順。

チャレンジ問題

マージソートを使って、配列内の「反転ペア」（i < j だが arr[i] > arr[j]）の数を数える関数を実装してください。

参考リンク

次回予告: Day 7では「木構造と二分探索木」について学びます。階層的なデータを効率的に管理する方法を理解しましょう。