Ein für alle Mal prüfen
Lineare Suche: Jedes Einzelne prüfen
Stellen Sie sich vor, Sie haben 10 Karten mit der Vorderseite nach unten, nummeriert von 1 bis 10, in zufälliger Reihenfolge gemischt.
Sie möchten die Karte mit der Nummer 7 finden.
Sie drehen die Karten eine nach der anderen, von links nach rechts, bis Sie sie finden.
| Szenario | Notwendige Drehungen |
|----------|---------------------|
| Best case | 1 Drehung (glücklicher erster Versuch!) |
| Worst case | 10 Drehungen (es war die letzte Karte) |
| Durchschnitt | etwa 5 Drehungen |
Stellen Sie sich jetzt 100 Karten vor. Durchschnitt: etwa 50 Drehungen.
1000 Karten? Durchschnitt: etwa 500 Drehungen.
Sie erkennen den Musterablauf? Doppelten Sie die Karten, doppelt sich die Arbeit. Die Arbeit wächst in einer geraden Linie.
Informatiker nennen dies lineare Suche - linear bedeutet, dass die Arbeit wie eine Linie wächst: stetig und vorhersehbar.
Lineare Suche funktioniert bei jeder Liste, sortiert oder unsortiert. Das macht sie einfach. Aber sie kann langsamer werden.
Wie viele Namen?
Sie haben eine Klasseliste von 20 Namen geschrieben, in zufälliger Reihenfolge.
Sie müssen den Namen Zoe finden.
Sie prüfen die Namen eine nach der anderen, von der oberen Liste herunter.
Die Liste halbieren
Binärische Suche: Zum Mittelpunkt springen
Die Binärsuche hat eine Regel: Die Liste muss zuerst sortiert werden.
Wenn Ihre Liste von 20 Namen von A bis Z geht, können Sie die Binärsuche verwenden.
Wie es funktioniert: Öffnen Sie den mittleren Namen (Name #10). Fragt: Ist Zoe vor oder nach diesem Namen?
Z kommt am Ende des Alphabets nahe, daher kommt Zoe nach dem Mittelpunkt. Werfen Sie die erste Hälfte. Jetzt haben Sie nur noch Namen 11-20.
Überprüfen Sie den Mittelpunkt der 10 Namen (Name #15). Z kommt nach M, daher kommt Zoe nach Name #15. Werfen Sie die Namen 11-14. Jetzt haben Sie die Namen 16-20.
Kürzen Sie weiterhin die Hälfte. Jeder Check entfernt die Hälfte der verbleibenden Namen.
| Liste | Max. Checks mit Binärsuche |
|-------|-----------------------------|
| 20 Namen | bis zu 5 Checks |
| 1.000 Namen | bis zu 10 Checks |
| 1.000.000 Namen | bis zu 20 Checks |
Vergleichen Sie das mit der linearen Suche bei 1.000.000 Namen: ein durchschnittliches 500.000 Checks.
Binärsuche kürzt die Liste jedes Mal um die Hälfte. Wiederholtes Kürzen bringt 1 sehr schnell - das ist, warum es so schnell bleibt.
Finden von 'fig' in einer sortierten Liste
Hier ist eine sortierte Liste von 8 Wörtern:
1. Apfel 2. Banane 3. Kirsche 4. Datte 5. Johannisbeere 6. Feige 7. Traube 8. Honigmelone
Sie möchten Feige mit der Binärsuche finden.
Denken Sie daran: Überprüfen Sie den Mittelpunkt, fragen Sie, ob Ihre Zielpunkte vor oder nach ihm stehen, und kürzen Sie dann die Liste um die Hälfte.
Nachbarn austauschen, um in der Reihenfolge zu sein
Blasensortierung: Nachbarn vergleichen und austauschen
Die Blasensort ordnet eine Liste durch das Vergleichen zweier benachbarter Elemente auf einmal.
Wenn zwei Nachbarn aus der Reihenfolge geraten - tauschen sie aus.
Macht weiterhin Durchgänge durch die Liste, bis nichts mehr getauscht werden muss.
Beispiel: sortiere [5, 3, 8, 1]
Durchgang 1:
- Vergleiche 5 & 3. 5 > 3, also tauschen → [3, 5, 8, 1]
- Vergleiche 5 & 8. 5 < 8, kein Tausch → [3, 5, 8, 1]
- Vergleiche 8 & 1. 8 > 1, also tauschen → [3, 5, 1, 8]
Durchgang 2:
- Vergleiche 3 & 5. OK → [3, 5, 1, 8]
- Vergleiche 5 & 1. 5 > 1, tauschen → [3, 1, 5, 8]
- Vergleiche 5 & 8. OK → [3, 1, 5, 8]
Durchgang 3:
- Vergleiche 3 & 1. 3 > 1, tauschen → [1, 3, 5, 8]
- Vergleiche 3 & 5. OK. Vergleiche 5 & 8. OK.
Fertig! [1, 3, 5, 8] ✓
Achtung: Das größte Zahl blasen am Ende der Liste auf jedem Durchgang. Das ist, wie Bubble Sort seinen Namen bekommen hat.
Bubble sort funktioniert. Es ist nicht das Schnellste für große Listen, aber es ist einfach zu verstehen - perfekt zum Lernen.
Sortiere [4, 2, 7, 1] mit Bubble Sort
Sortiere diese Liste mit Blasensort: [4, 2, 7, 1]
Zeige die Liste nach jedem Durchgang. Zähle, wie viele Durchgänge es braucht, um fertig zu sein.