第2章: アルゴリズムと論理 - ソートと探索

膨大なデータをどのようにソートし、探索するかによって、プログラムの性能は天と地ほどの差が出ます。現代の検索エンジンや推薦システムの裏側には、高度なソートおよび探索アルゴリズムが隠されています。

1. データソート (Sorting)

ソートとは、データを特定の基準（昇順、降順）に従って並べるプロセスです。

ソートの核心原理：分割統治 (Divide & Conquer)

複雑な問題を小さな問題に分割して解決する方式です。クイックソートやマージソートはこの原理を利用することで、$O(n \log n)$という効率的な速度を達成しています。

2. データ探索 (Searching)

探索とは、データ集合の中から目的のデータを見つけ出すプロセスです。

(1) 線形探索 (Linear Search)

先頭から順番に一つずつ比較していく方式です。

• 特徴: データがソートされていなくても使用可能。
• 性能: $O(n)$ (データが増えるほど、探索時間も比例して増加)。

(2) 二分探索 (Binary Search)

ソートされたデータの ==中間値== を基準に、探索範囲を半分ずつ絞り込んでいく方式です。

• 特徴: 必ずデータが ソート されている必要がある。
• 性能: $O(\log n)$ (データが100万個あっても、わずか20回の比較で探索可能)。

3. なぜアルゴリズムの効率性が重要なのか？

データが1,000倍に増えたとき、$O(n)$ のアルゴリズムは1,000倍遅くなりますが、$O(n^2)$ のアルゴリズムは1,000,000倍も遅くなります。アルゴリズムの選択は単なるコーディングテクニックではなく、システムの「限界」を決定する重要な設計要素です。

キーチェックリスト

• データをソートする際、ピボット(Pivot)値を基準に左右に分けてソートする方式は？（正解：クイックソート）
• ソートされたデータの中間値を確認しながら、探索範囲を半分に減らし続ける探索法は？（正解：二分探索）
• データが $n$ 個のとき、二分探索の時間計算量は何ですか？（正解：$O(\log n)$）