一つずつチェック
線形検索：一つずつチェック
10枚のカードがあり、1から10までの番号が書かれています。ランダムに並べられています。
7という番号のカードを見つけたいと思います。
左から右にカードを一つずつひっくり返し、見つかるまで続けます。
| シナリオ | フリップが必要な回数 |
|----------|-------------|
| ベストケース | 1フリップ (幸運な最初の試み!) |
| ワーストケース | 10フリップ (最後のカードでした) |
| 平均 | 5フリップほど |
100枚のカードを想像してみましょう。平均で約 50フリップ。
1000枚のカード？ 平均で約 500フリップ。
見出しがわかるでしょうか？ カードを2倍にすると、仕事も2倍になります。仕事は直線的に増加します。
コンピューターサイエンスでこの 線形検索 と呼ばれています - 線形は、仕事が直線的に増加することを意味します。安定して予測可能です。
線形検索は、ソートされたリストや未ソートのリストでも使用できます。これがその利点です。しかし、速度が遅くなることがあります。
名前の数
20人の名前が書かれたクラスリストがあります。
名前 'Zoe' を見つけたいと思います。
名前を一つずつチェックし、リストの先頭から下に進みます。
リストの半分に切り替える
二分探索: 中央にジャンプ
二分探索のルールは一つ: リストは先に並べ替える必要があります。
20人の名前のリストが A から Z になると、binary search を使用できます。
どのように機能しますか: 中央の名前 (名前 #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 回のチェック |
linear search を使用した 1,000,000 名の場合、平均で 500,000 回のチェック が必要です。
二分探索は、各回でリストを半分に切り替えます。半分に切り替えを繰り返すと、1 に非常に速く到達するため、これがなぜ速いままになる理由です。
並べ替えられたリストで 'fig' を見つける
ここに 8 個の単語の並べ替えられたリストがあります:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
binary search を使用して 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]
各パス後にリストを表示。完了するために必要なパスの数をカウントしてください。