アルゴリズムって、すごく難しいプログラムのことですか？
実は「問題を解くための手順」のことなんだ。中でも定番が「データを探す」と「データを並べ替える」。辞書を引くときやトランプを並べるとき、みんな無意識に使っているよ。
探索と整列とは
- 探索（サーチ）：たくさんのデータの中から、目的のデータを見つけること
- 整列（ソート）：データを小さい順（昇順）や大きい順（降順）に並べ替えること
同じ結果を得るにも、手順によって かかる手間（比較の回数） が大きく変わります。試験では、その違いが問われます。
線形探索：先頭から1つずつ
線形探索 は、データを 先頭から順番に1つずつ 調べる方法です。本棚の端から1冊ずつ背表紙を見ていくイメージです。
- 長所：データが並んでいなくても使える。手順が単純
- 短所：データが多いと時間がかかる
データが n 件のとき（目的のデータが必ずある場合）
- 最大の比較回数：n 回（いちばん最後にあった場合）
- 平均の比較回数：約 n/2 回
2分探索：真ん中で比べて半分を捨てる
2分探索 は、整列済みのデータ に対して、真ん中の値と比べて、探す範囲を半分に絞り込む ことをくり返す方法です。国語辞典を真ん中あたりで開き、「探したい言葉はもっと後ろだ」と半分を捨てていくのと同じです。
15件のデータでも、最大4回の比較で見つかります。データが2倍になっても、比較回数は 1回増えるだけ です。
2分探索の最大比較回数 の求め方
「2k ≦ データ件数 ＜ 2k＋1」となる k を探し、k ＋ 1 回
- 15件：23＝8 ≦ 15 ＜ 16 → 3 ＋ 1 ＝ 4回
- 100件：26＝64 ≦ 100 ＜ 128 → 6 ＋ 1 ＝ 7回
- 1,000件：29＝512 ≦ 1,000 ＜ 1,024 → 9 ＋ 1 ＝ 10回
2分探索は データが整列されていないと使えない。バラバラのデータに使うには、先に整列する手間がかかる。
ハッシュ法
ハッシュ法 は、データの値から計算式（ハッシュ関数）で 格納場所を直接求める 方法です。うまく働けば1回の計算で目的の場所がわかりますが、別のデータが同じ格納場所になる 衝突 への対策が必要です（同じ場所になるデータどうしを シノニム といいます）。
整列の代表的な方法
| 方法 | 手順のイメージ | 身近な例え |
|---|---|---|
| バブルソート（交換法） | 隣り合う2つを比べ、順番が逆なら交換。これをくり返す | 泡（バブル）が水面に浮かぶように、大きい値が端へ移動する |
| 選択ソート（選択法） | 未整列の中から最小値を選んで、先頭と交換する | 背の順で、残った中で一番低い人を前に呼ぶ |
| 挿入ソート（挿入法） | 整列済みの部分の正しい位置に、次のデータを挿入する | トランプの手札を、1枚ずつ正しい位置に差し込む |
| クイックソート | 基準値を決め、それより小さいグループと大きいグループに分けることをくり返す | クラスを「150cm未満」「以上」に分け、さらに細かく分ける |
| マージソート | データを細かく分割し、整列しながら併合（マージ）する | 2つの整列済みの山を、先頭から比べて1つにまとめる |
選択ソート で 6, 2, 9, 4 を小さい順に
- 全体の最小値 2 を先頭の 6 と交換 → 2, 6, 9, 4
- 残り（6, 9, 4）の最小値 4 を 6 と交換 → 2, 4, 9, 6
- 残り（9, 6）の最小値 6 を 9 と交換 → 2, 4, 6, 9（完了）
バブルソートと選択ソートの区別がつきません…。
バブルソートは「隣どうし」だけを比べて、こまめに交換する。選択ソートは「残り全体から最小値を探して」、1回だけ交換する。キーワードは「隣」か「最小」かだよ。
一般に、データ件数が多いときは クイックソート や マージソート の方が、バブル・選択・挿入ソートより速く整列できます。
試験に出るポイント
- 線形探索：先頭から順に。最大 n 回、平均 約 n/2 回。整列していなくても使える
- 2分探索：整列済みが前提。中央と比べて半分を捨てる。最大の比較回数は件数が2倍になっても1回増えるだけ
- ハッシュ法：計算で格納場所を求める。同じ場所になる衝突に注意
- バブルソート＝隣どうしを交換、選択ソート＝最小値を選んで交換、挿入ソート＝正しい位置に差し込む
- クイックソート＝基準値で分割、マージソート＝分割して併合