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 | benötigte 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.
1.000 Karten? Durchschnitt: etwa 500 Drehungen.
Sie erkennen den Musterablauf? Doppelten Sie die Karten, doppelte Arbeit. Die Arbeit wächst in einer geraden Linie.
Informatiker nennen dies lineare Suche - linear bedeutet, dass die Arbeit wie eine Linie wächst: gleichmäßig und vorhersehbar.
Lineare Suche funktioniert bei jeder Liste, sortiert oder nicht. Das macht sie einfach. Aber sie kann langsam werden.
Wie viele Namen?
Sie haben eine Klassensliste mit 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
Binäre Suche 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). Fragten Sie: 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 dieser 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 in der Hälfte. Jeder Check entfernt die Hälfte der verbleibenden Namen.
| Liste | Max. Checks mit Binärsuche |
|-------|-----------------------------|
| 20 Namen | maximal 5 Checks |
| 1.000 Namen | maximal 10 Checks |
| 1.000.000 Namen | maximal 20 Checks |
Vergleichen Sie das mit der linearen Suche bei 1.000.000 Namen: Durchschnittlich 500.000 Checks.
Binäre Suche teilt die Liste jedes Mal in der Hälfte. Wiederholtes Kürzen bringt 1 sehr schnell - das ist, warum es so schnell bleibt.
Finden Sie 'fig' in einer sortierten Liste
Hier ist eine sortierte Liste von 8 Wörtern:
1. Apfel 2. Banane 3. Kirsche 4. Date 5. Weißdornbeere 6. Fig 7. Traube 8. Honigmelone
Sie möchten Fig mit der Binärsuche finden.
Denken Sie daran: Überprüfen Sie den Mittelpunkt, fragen Sie, ob Ihr Ziel vor oder nach ihm ist, und kürzen Sie dann die Liste in der Hälfte.
Nachbarn austauschen, um geordnet zu sein
Blasensortierung: Nachbarn vergleichen & austauschen
Das Blasen-Sortierverfahren ordnet eine Liste durch den Vergleich zweier benachbarter Elemente nach.
Wenn zwei Nachbarn falsch geordnet sind - tauschen sie aus.
Machen Sie immer wieder 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 Element "blasen" sich auf das Ende der Liste bei jedem Durchgang. So heißt das Blasen-Sortierverfahren auch.
Das Blasen-Sortierverfahren funktioniert. Es ist jedoch nicht das Schnellste für große Listen, aber es ist einfach zu verstehen - perfekt zum Erlernen.
Sortiere [4, 2, 7, 1] mit Blasen-Sortierverfahren
Sortiere diese Liste mit dem Blasen-Sortierverfahren: [4, 2, 7, 1]
Zeige die Liste nach jedem Durchgang. Zähle, wie viele Durchgänge es braucht, um fertig zu sein.