探索と整列のアルゴリズム
こんにちは！この章では、コンピュータが大量のデータの中から目的のものを見つけ出したり、バラバラなデータを順番に並べ替えたりする「手順（アルゴリズム）」について学びます。プログラミングの要とも言える部分ですが、トランプのカードを整理する様子をイメージすれば、決して難しくありません。一歩ずつ一緒に理解していきましょう！
1. 探索アルゴリズム（データを探す）
たくさんのデータの中から、目的の値がどこにあるかを探し出すことを探索といいます。代表的な2つの方法を覚えましょう。
① 線形探索法（リニアサーチ）
データの端から順番に、目的のものが見つかるまで1つずつ確認していく最も単純な方法です。
- 特徴：データがバラバラに並んでいても使えます。
- 手間：データの数を \(n\) 個とすると、最大で \(n\) 回の比較が必要です。
共通テスト用プログラム表記の例（線形探索）：
(1) target = 75
(2) Data = [10, 45, 75, 20, 90]
(3) pos = -1
(4) i を 0 から 4 まで 1 ずつ増やしながら繰り返す：
(5) ｜ もし Data[i] ＝ target ならば：
(6) ｜ ｜ pos = i
(7) ｜ └ 表示する("見つかりました。位置は", pos)
② 二分探索法（バイナリサーチ）
真ん中の値を確認し、目的の値がそれより大きいか小さいかで、探す範囲を半分に絞り込んでいく効率的な方法です。
- 特徴：データが必ず昇順（小さい順）または降順（大きい順）に並んでいる必要があります。
- 手間：範囲が半分ずつになっていくため、線形探索よりもずっと速く見つけることができます。
【ポイント】
二分探索は「事前の準備（並べ替え）」が重要！
バラバラのデータには使えないという点に注意しましょう。
【豆知識】
辞書で単語を調べるとき、パッと真ん中あたりを開いて「あ、もっと後ろだな」と範囲を絞り込みますよね？それがまさに「二分探索」の考え方です！
2. 整列アルゴリズム（データを並べ替える）
バラバラなデータを一定の規則（小さい順など）に並べ替えることを整列（ソート）といいます。ここでは代表的な3つの手法を解説します。
① 基本交換法（バブルソート）
隣り合う要素を比較して、順序が逆なら入れ替える、という操作を繰り返す方法です。大きい値がプクプクと泡（バブル）のように端へ移動していくのが名前の由来です。
- 手順：右端から隣同士を比較し、小さい方を左へ送る操作を繰り返します。
② 基本選択法（選択ソート）
バラバラなデータの中から「最小値」を探し出し、それを左端の要素と入れ替える方法です。
- 手順：残っているデータの中で一番小さいものを探し、まだ整列していない範囲の左端に置きます。
③ 基本挿入法（挿入ソート）
「整列済みの列」に、新しい要素を適切な位置へ「割り込ませる（挿入する）」方法です。
- 手順：トランプを手札に1枚ずつ、正しい位置に差し込んでいく感覚に似ています。
【よくある間違い】
「選択法」と「挿入法」は名前が似ていますが別物です！
・選択法：全体から一番小さいものを「選んで」くる。
・挿入法：新しい1枚を、すでに並んでいる列のどこに入れるか「差し込む」。
この違いを意識しましょう。
3. アルゴリズムの評価（どちらが効率的？）
アルゴリズムは「正しく動くこと」だけでなく、「効率が良いこと」も大切です。効率を考える基準の1つが、データの数 \(n\) が増えたときに、比較などの操作回数がどれくらい増えるか、という点です。
探索の効率の比較
- 線形探索：比較回数は \(n\) に比例します。
- 二分探索：比較回数は \(\log_{2} n\) に比例します（\(n\) が増えても回数はあまり増えません）。
整列の効率
今回紹介した3つの整列法（バブル・選択・挿入）は、どれもデータの数 \(n\) が2倍になると、計算の手間はおよそ \(n^{2}\)（4倍）になるという特徴があります。
【ポイント】
効率を考えるときは、「最悪の場合（運が悪いとき）」に何回の操作が必要になるかを考えるのが基本です。
まとめ：この章の総仕上げ
最初はアルゴリズムの流れを追うのが大変かもしれませんが、自分で小さな数字を使って、紙の上でデータの動きをシミュレーションしてみるのが一番の近道です！
- 線形探索は「端から順に」、二分探索は「真ん中で半分に（要・整列済み）」。
- バブルソートは「隣同士を交換」。
- 選択ソートは「最小値を探して持ってくる」。
- 挿入ソートは「正しい位置に割り込ませる」。
「この場合はどのアルゴリズムが使えるかな？」と考える癖をつければ、共通テストのプログラミング問題も怖くありません。コツコツ頑張りましょう！