1つずつ確認する
線形探索：1つずつチェック
10枚のカードが顔を下にして置いてあり、1から10までの番号が付いていて、ランダムに混ぜられているとします。
番号7が書いたカードを見つけたいのです。
左から右へ1枚ずつカードをめくって、それを見つけるまで続けます。
| シナリオ | 必要なめくり回数 |
|---|---|
| 最良の場合 | 1回のめくり（幸運にも最初の1回！） |
| 最悪の場合 | 10回のめくり（最後のカードだった） |
| 平均 | 約5回のめくり |
今、100枚のカードがあるとします。平均：約50回のめくり。
1,000枚のカード？平均：約500回のめくり。
パターンが見えますか？カード数が2倍になると、仕事量も2倍になります。仕事は直線的に増えます。
コンピュータ科学者は、これを線形探索と呼びます。線形は、仕事が一直線で増えることを意味します：一定で予測可能です。
線形探索はどのリストでも機能し、ソート済みか否かは関係ありません。それが単純性です。しかし遅くなる可能性があります。
何人の名前？
クラスの名簿に20人の名前がランダムな順序で書かれています。
名前Zoeを見つける必要があります。
リストの上から下へ、1つずつ名前をチェックします。
リストを半分に削減
二分探索：中央にジャンプ
二分探索には1つのルールがあります：リストは最初にソートしておく必要があります。
20人の名前がAからZの順になっていれば、二分探索を使用できます。
仕組み：中央の名前（名前＃10）を開きます。質問：Zoeはこの名前の前ですか、後ろですか？
Zはアルファベットの終わり付近にあるため、Zoeは中央より後ろです。最初の半分を捨てます。これで名前11～20だけが残ります。
それら10の名前の中央をチェックします（名前＃15）。ZはMの後ろなので、Zoeは名前＃15の後ろです。名前11～14を捨てます。これで名前16～20だけが残ります。
半分に削減し続けます。各チェックで残りの名前の半分を削除します。
| リストサイズ | 二分探索での最大チェック数 |
|---|---|
| 20人の名前 | 最大5回のチェック |
| 1,000人の名前 | 最大10回のチェック |
| 1,000,000人の名前 | 最大20回のチェック |
これを1,000,000人の名前の線形探索と比較します：平均500,000回のチェック。
二分探索は毎回リストを半分にします。繰り返し半分にすることで、1に非常に迅速に到達します。それが二分探索が非常に高速である理由です。
ソート済みリストで「fig」を見つけます
8つの単語のソート済みリストです：
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
二分探索を使ってfigを見つけたいです。
覚えておいてください：中央をチェックし、ターゲットが前なのか後ろなのかを尋ね、リストを半分に削減します。
隣同士を入れ替えて順序付けする
バブルソート：隣同士を比較して入れ替える
バブルソートは、一度に2つの隣同士のアイテムを比較することでリストを順序付けします。
2つの隣同士のアイテムが順序が正しくなければ、それらを入れ替えます。
何も入れ替える必要がなくなるまで、リストを何度もパスしていきます。
例：[5, 3, 8, 1]をソート
パス1：
- 5と3を比較します。5 > 3なので、入れ替え → [3, 5, 8, 1]
- 5と8を比較します。5 < 8なので、入れ替えなし → [3, 5, 8, 1]
- 8と1を比較します。8 > 1なので、入れ替え → [3, 5, 1, 8]
パス2：
- 3と5を比較します。OK → [3, 5, 1, 8]
- 5と1を比較します。5 > 1なので、入れ替え → [3, 1, 5, 8]
- 5と8を比較します。OK → [3, 1, 5, 8]
パス3：
- 3と1を比較します。3 > 1なので、入れ替え → [1, 3, 5, 8]
- 3と5を比較します。OK。5と8を比較します。OK。
完了！[1, 3, 5, 8] ✓
注意：最大の数字は各パスでリストの終わりまでバブルアップします。それはバブルソートが名前の由来です。
バブルソートは機能します。大きなリストの場合、最速ではありませんが、理解しやすいため、学習に最適です。
バブルソートで[4, 2, 7, 1]をソート
バブルソートを使ってこのリストをソートします：[4, 2, 7, 1]
各パスの後のリストを表示します。完了するまでにいくつのパスがかかるかを数えます。