Hochneu im Katalog 2025
Such- und Sortieralgorithmen
Lineare/Binäre Suche, Bubble-/Selection-/Insertion-Sort – explizit im Katalog seit 2025.
Warum Priorität „Hoch"? Häufig Teil der Prüfung (60–79%) oder bringt viele Punkte.
Lernziele
- Lineare und binäre Suche implementieren und vergleichen
- Bubble-, Selection- und Insertion-Sort erkennen und ausführen
- Laufzeit in O-Notation benennen
Suche
Lineare Suche – O(n)
pseudocode
FUNKTION lineareSuche(liste, ziel) → INT
FÜR i VON 0 BIS länge(liste) - 1 TUE
WENN liste[i] = ziel DANN GIB i zurück
ENDE FÜR
GIB -1 zurück
ENDE FUNKTIONBinäre Suche – O(log n), nur auf sortierter Liste
pseudocode
FUNKTION binaereSuche(sortListe, ziel) → INT
links ← 0
rechts ← länge(sortListe) - 1
SOLANGE links <= rechts TUE
mitte ← (links + rechts) / 2 // Ganzzahldivision
WENN sortListe[mitte] = ziel DANN GIB mitte zurück
WENN sortListe[mitte] < ziel DANN links ← mitte + 1
SONST rechts ← mitte - 1
ENDE SOLANGE
GIB -1 zurück
ENDE FUNKTIONSortieralgorithmen
Bubble Sort – O(n²)
Vergleicht benachbarte Paare, vertauscht sie bei Bedarf. Nach jedem Durchlauf »blubbert« der größte Wert ans Ende.
pseudocode
FÜR i VON 0 BIS n - 2 TUE
FÜR j VON 0 BIS n - 2 - i TUE
WENN a[j] > a[j+1] DANN tausche a[j], a[j+1]
ENDE FÜR
ENDE FÜRSelection Sort – O(n²)
Findet in jedem Durchlauf das Minimum des Restes und tauscht es nach vorn.
pseudocode
FÜR i VON 0 BIS n - 2 TUE
minIdx ← i
FÜR j VON i + 1 BIS n - 1 TUE
WENN a[j] < a[minIdx] DANN minIdx ← j
ENDE FÜR
tausche a[i], a[minIdx]
ENDE FÜRInsertion Sort – O(n²), aber best case O(n)
Elementweise an die richtige Stelle in der sortierten linken Teilliste einfügen.
pseudocode
FÜR i VON 1 BIS n - 1 TUE
key ← a[i]
j ← i - 1
SOLANGE j >= 0 UND a[j] > key TUE
a[j+1] ← a[j]
j ← j - 1
ENDE SOLANGE
a[j+1] ← key
ENDE FÜRLaufzeit-Überblick
| Algo | Best | Durchschn. | Worst | Stabil? |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | ja |
| Selection | O(n²) | O(n²) | O(n²) | nein |
| Insertion | O(n) | O(n²) | O(n²) | ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | nein |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | ja |
Übungen
Eine AntwortWelche Laufzeit hat binäre Suche?
Eine AntwortWelcher Sort ist im Best Case O(n)?