探索と整列｜線形探索と二分探索の違い、選択ソート・バブルソートの仕組み
たくさんのデータの中から目的の値を見つける手順を探索、データを大きさの順に並べ替える手順を整列（ソート）といいます。共通テストでは、線形探索と二分探索の違い、整列の手順の途中経過、比較の回数がよく問われます。
線形探索
線形探索 は、データを先頭から順に1つずつ調べる方法です。
- データが整列されていなくても使える
- n 個のデータなら、比較回数は最大 n 回、平均で約 n/2 回
単純で分かりやすい反面、データが多いと時間がかかります。
二分探索
二分探索 は、大きさの順に並んだデータの真ん中と比べ、探す範囲を半分ずつ絞り込む方法です。
例：[3, 18, 29, 33, 48, 52, 62, 77, 89, 97] から 62 を探す
- 範囲は添字 0〜9。真ん中は (0 + 9) ÷ 2 = 4 で、Data[4] = 48。62 の方が大きいので、右半分（添字 5〜9）に絞る
- 真ん中は (5 + 9) ÷ 2 = 7 で、Data[7] = 77。62 の方が小さいので、左側（添字 5〜6）に絞る
- 真ん中は (5 + 6) ÷ 2 = 5 で、Data[5] = 52。62 の方が大きいので、添字 6 だけになる
- Data[6] = 62 で見つかった
比較回数の比べ方
1回比べるたびに範囲が半分になるので、二分探索の比較回数は最大でも約 log₂n 回です。
| データの個数 | 線形探索（最大） | 二分探索（最大） |
|---|---|---|
| 10個 | 10回 | 4回 |
| 1,000個 | 1,000回 | 10回 |
| 100万個 | 100万回 | 20回 |
2¹⁰ = 1024 なので、1000個なら約10回で見つかります。データが多いほど、差は大きくなります。
共通テスト用プログラム表記で読む
二分探索は、共通テスト用プログラム表記 で次のように書けます。
hidari = 0 , migi = 要素数(Data) - 1
mitsukatta = 0
hidari <= migi and mitsukatta == 0 の間繰り返す:
| aida = (hidari + migi) ÷ 2
| もし Data[aida] == atai ならば:
| | mitsukatta = 1
| そうでなくもし Data[aida] < atai ならば:
| | hidari = aida + 1
| そうでなければ:
⎿ ⎿ migi = aida - 1÷ は整数の商を求める演算子で、真ん中の添字を求めるのに使っています。目的の値が真ん中より大きければ左端（hidari）を、小さければ右端（migi）を動かして、範囲を狭めていきます。
整列（ソート）
整列は、データを小さい順（昇順）や大きい順（降順）に並べ替えることです。二分探索を使うには、データが整列されている必要があります。代表的な方法を、[5, 3, 8, 1] を昇順に並べる例で見てみましょう。
選択ソート
残りの中から最小値を探し、残りの先頭と入れ替えることを繰り返します。
| 回 | 探す範囲 | 最小値 | 入れ替え後 |
|---|---|---|---|
| 1回目 | 5, 3, 8, 1 | 1 | 1, 3, 8, 5 |
| 2回目 | 3, 8, 5 | 3 | 1, 3, 8, 5（入れ替えなし） |
| 3回目 | 8, 5 | 5 | 1, 3, 5, 8 |
最小値を探す処理は、「配列と関数」の「最小値の位置を探す」型そのものです。
バブルソート
隣り合う2つを比べ、順番が逆なら入れ替えることを、端から端まで繰り返します。1周するごとに、最大値が右端に移動します（泡が浮かび上がるように見えることから、この名前があります）。
| 周 | 比較と入れ替え | 周の終わり |
|---|---|---|
| 1周目 | (5,3)入替 → (5,8)そのまま → (8,1)入替 | 3, 5, 1, 8 |
| 2周目 | (3,5)そのまま → (5,1)入替 | 3, 1, 5, 8 |
| 3周目 | (3,1)入替 | 1, 3, 5, 8 |
そのほかの整列
| 方法 | 考え方 |
|---|---|
| 挿入ソート | 整列済みの部分の正しい位置に、次のデータを差し込んでいく。トランプの手札を並べるときの方法 |
| クイックソート | 基準の値を決め、それより小さいグループと大きいグループに分けることを繰り返す。データが多いときに速い |
比較回数
選択ソートとバブルソートでは、データが n 個のとき、比較回数は
(n − 1) ＋ (n − 2) ＋ … ＋ 1 ＝ n × (n − 1) ÷ 2 回
です。上の例（4個）では 3 ＋ 2 ＋ 1 ＝ 6 回でした。データが10個なら45回、100個なら4,950回と、データが2倍になると比較回数は約4倍になります。データが多いときは、クイックソートなどの速い方法が使われます。
共通テストでの出題
- 探索の手順と比較回数：二分探索で、何回目の比較で見つかるか、そのとき範囲の左端・右端はいくつか、を問う問題。
- 整列の途中経過：「バブルソートの1周目が終わった時点の並び」のように、途中の状態を問う問題。
- プログラムの空欄：二分探索や整列のプログラムの、範囲を狭める処理や入れ替えの処理を埋める問題。
よくある間違い
- 二分探索をデータが整列されていないときに使う：二分探索は、整列済みのデータでしか使えません。
- 真ん中の添字の計算：
÷は小数点以下を切り捨てた商です。(5 + 6) ÷ 2 は 5 です。 - 比較回数と入れ替え回数の混同：選択ソートでは、比較は毎回行いますが、入れ替えは最小値が先頭にないときだけです。
まとめ
- 線形探索は先頭から順に調べ、最大 n 回。整列されていなくても使える
- 二分探索は整列済みのデータを半分ずつ絞り込み、最大約 log2n 回
- 選択ソートは「最小値を探して先頭と入れ替え」、バブルソートは「隣どうしを比べて入れ替え」
- 選択ソート・バブルソートの比較回数は n × (n − 1) ÷ 2 回