Nacheinander überprüfen
Lineare Suche: Überprüfe jede nacheinander
Stellen dir vor, du hast 10 verdeckte Karten, nummeriert von 1 bis 10, in zufälliger Reihenfolge durcheinander.
Du möchtest die Karte mit der Nummer 7 finden.
Du deckst Karten nacheinander auf, von links nach rechts, bis du sie findest.
| Szenario | Umdrehungen erforderlich |
|---|---|
| Best case | 1 Umdrehung (Glücklicher erster Versuch!) |
| Worst case | 10 Umdrehungen (es war die letzte Karte) |
| Durchschnitt | etwa 5 Umdrehungen |
Stellen dir jetzt 100 Karten vor. Durchschnitt: etwa 50 Umdrehungen.
1.000 Karten? Durchschnitt: etwa 500 Umdrehungen.
Siehst du das Muster? Doppelte 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: stetig & vorhersehbar.
Lineare Suche funktioniert auf JEDER Liste, sortiert oder nicht. Das macht es einfach. Aber es kann langsam werden.
Wie viele Namen?
Du hast eine Klassenliste mit 20 Namen, die in zufälliger Reihenfolge geschrieben sind.
Du musst den Namen Zoe finden.
Du überprüfst Namen nacheinander, von oben nach unten auf der Liste.
Teile die Liste in zwei Hälften
Binäre Suche: Springe in die Mitte
Binäre Suche hat eine Regel: Die Liste muss zuerst sortiert sein.
Wenn deine Liste von 20 Namen von A bis Z geht, kannst du binäre Suche verwenden.
Wie es funktioniert: Öffne den mittleren Namen (Name #10). Frage: Kommt Zoe vor oder nach diesem Namen?
Z kommt am Ende des Alphabets, also kommt Zoe NACH der Mitte. Verwirf die erste Hälfte. Jetzt hast du nur noch Namen 11-20 übrig.
Überprüfe die Mitte dieser 10 Namen (Name #15). Z kommt nach M, also kommt Zoe nach Name #15. Verwirf Namen 11-14. Jetzt hast du Namen 16-20.
Bleib dabei, in zwei Hälften zu schneiden. Jede Überprüfung entfernt die Hälfte der verbleibenden Namen.
| Listengröße | Max Überprüfungen mit binärer Suche |
|---|---|
| 20 Namen | höchstens 5 Überprüfungen |
| 1.000 Namen | höchstens 10 Überprüfungen |
| 1.000.000 Namen | höchstens 20 Überprüfungen |
Vergleiche das mit linearer Suche auf 1.000.000 Namen: ein Durchschnitt von 500.000 Überprüfungen.
Binäre Suche teilt die Liste jedes Mal in zwei Hälften. Das wiederholte Halbieren erreicht 1 sehr schnell — deshalb bleibt es so schnell.
Finde 'Feige' in einer sortierten Liste
Hier ist eine sortierte Liste von 8 Wörtern:
1. Apfel 2. Banane 3. Kirsche 4. Dattel 5. Holunderbeere 6. Feige 7. Traube 8. Honigmelone
Du möchtest Feige mit binärer Suche finden.
Denk dran: Überprüfe die Mitte, frage, ob dein Ziel davor oder danach kommt, dann teile die Liste in zwei Hälften.
Nachbarn in Ordnung austauschen
Bubble Sort: Vergleiche Nachbarn & Tausche aus
Bubble Sort ordnet eine Liste, indem es jeweils zwei benachbarte Elemente vergleicht.
Wenn zwei Nachbarn nicht in Ordnung sind — tausche sie aus.
Mache 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 tausche → [3, 5, 8, 1]
- Vergleiche 5 & 8. 5 < 8, kein Tausch → [3, 5, 8, 1]
- Vergleiche 8 & 1. 8 > 1, also tausche → [3, 5, 1, 8]
Durchgang 2:
- Vergleiche 3 & 5. OK → [3, 5, 1, 8]
- Vergleiche 5 & 1. 5 > 1, tausche → [3, 1, 5, 8]
- Vergleiche 5 & 8. OK → [3, 1, 5, 8]
Durchgang 3:
- Vergleiche 3 & 1. 3 > 1, tausche → [1, 3, 5, 8]
- Vergleiche 3 & 5. OK. Vergleiche 5 & 8. OK.
Fertig! [1, 3, 5, 8] ✓
Beachte: Die größte Zahl perlt bei jedem Durchgang zum Ende der Liste. So erhält Bubble Sort seinen Namen.
Bubble Sort funktioniert. Es ist nicht das Schnellste für große Listen, aber es ist leicht zu verstehen — perfekt zum Lernen.
Sortiere [4, 2, 7, 1] mit Bubble Sort
Sortiere diese Liste mit Bubble Sort: [4, 2, 7, 1]
Zeige die Liste nach jedem Durchgang. Zähle, wie viele Durchgänge es braucht, um fertig zu werden.