Sortieren: Bubble, Selection, Insertion, Merge
Eine sortierte Liste ist Gold wert: sie macht binäre Suche möglich, vereinfacht das Finden von Duplikaten, beschleunigt viele andere Algorithmen. Doch wie kommt man von einer unsortierten Liste zu einer sortierten? Das ist die Frage, der diese Lektion sich widmet.
Sortier-Algorithmen sind eines der am meisten studierten Themen in der Informatik. Es gibt dutzende Varianten – jede mit eigenen Stärken und Schwächen. In dieser Lektion lernst du die vier wichtigsten kennen: Bubble Sort, Selection Sort, Insertion Sort und Merge Sort. Die ersten drei sind einfach zu verstehen, aber langsam. Merge Sort ist deutlich schneller – und zeigt eine völlig andere Strategie.
1) Alle vier im direkten Vergleich – live
Bevor wir in die Details der einzelnen Algorithmen einsteigen, schau dir alle vier in Aktion an. Wähle einen Algorithmus, klick „Start" und beobachte, wie er die Balken sortiert. Die Geschwindigkeit ist absichtlich verlangsamt, damit du den Ablauf nachvollziehen kannst:
2) Bubble Sort – das berühmteste, weil einfachste
Bubble Sort funktioniert wie sein Name suggeriert: kleinere Elemente „blubbern" wie Luftblasen nach oben. Vergleiche je zwei benachbarte Elemente. Wenn sie in falscher Reihenfolge stehen, tausche sie. Gehe die Liste so oft durch, bis kein Tausch mehr nötig ist.
n = laenge(liste)
FÜR i VON 1 BIS n - 1
FÜR j VON 1 BIS n - i
WENN liste[j] > liste[j+1] DANN
tausche(liste[j], liste[j+1])
ENDE WENN
ENDE FÜR
ENDE FÜR
ENDE FUNKTION
Bubble Sort ist Lehrbuch-Standard, aber in der Praxis fast nie eine gute Wahl. Er ist einfach zu verstehen und zu implementieren – aber bei großen Listen extrem langsam. Selbst die anderen einfachen Verfahren (Selection, Insertion) sind in der Regel besser.
3) Selection Sort – das Minimum suchen und voranstellen
Selection Sort hat eine andere Strategie: in jedem Durchgang suchst du das kleinste Element im verbleibenden Bereich und tauscht es nach vorne. Im ersten Durchgang findet sich also der globale Minimum-Wert auf Position 1. Im zweiten Durchgang das zweitkleinste auf Position 2. Und so weiter.
n = laenge(liste)
FÜR i VON 1 BIS n - 1
minIdx = i
FÜR j VON i + 1 BIS n
WENN liste[j] < liste[minIdx] DANN
minIdx = j
ENDE WENN
ENDE FÜR
tausche(liste[i], liste[minIdx])
ENDE FÜR
ENDE FUNKTION
Eine Besonderheit: Selection Sort hat immer dieselbe Anzahl Vergleiche, egal ob die Liste schon sortiert ist oder völlig zufällig. Dafür macht er aber sehr wenige Tausche (höchstens n-1). Das ist nützlich, wenn das Tauschen teuer ist (z.B. bei großen Objekten oder Dateien).
4) Insertion Sort – wie beim Karten-Sortieren
Insertion Sort imitiert, wie viele Menschen Spielkarten sortieren: du hältst die schon sortierte Hand und nimmst eine neue Karte. Du gehst sie von rechts durch und schiebst sie an die richtige Position ein. Genau das macht der Algorithmus mit den Elementen einer Liste.
n = laenge(liste)
FÜR i VON 2 BIS n
aktuell = liste[i]
j = i - 1
SOLANGE j > 0 UND liste[j] > aktuell TUE
liste[j+1] = liste[j] // nach rechts schieben
j = j - 1
ENDE SOLANGE
liste[j+1] = aktuell // einsortieren
ENDE FÜR
ENDE FUNKTION
Insertion Sort ist auf fast sortierten Listen sehr schnell – fast linear. Das macht ihn nützlich für „Online"-Sortierung: Daten kommen nacheinander rein und werden direkt in die sortierte Liste eingefügt. Auch ist er bei kleinen Listen (unter 20-50 Elemente) oft sogar schneller als die theoretisch besseren Algorithmen.
5) Merge Sort – Teile und Herrsche
Jetzt wird's spannend. Merge Sort verfolgt eine völlig andere Strategie: Divide and Conquer (Teile und herrsche). Statt die Liste schrittweise zu sortieren, wird sie immer wieder halbiert, bis nur noch Listen mit einem Element übrig sind (die sind trivial sortiert). Dann werden je zwei Hälften zu einer sortierten Liste „gemerged" (zusammengeführt).
Der Trick beim Merge: zwei bereits sortierte Listen zu einer sortierten zusammenzuführen ist schnell und einfach. Man vergleicht jeweils die ersten Elemente beider Listen und nimmt den kleineren. Wiederhole, bis beide leer sind. Das ist O(n) pro Merge-Schritt – und wir haben log(n) Ebenen. Macht insgesamt O(n log n) – dramatisch besser als die O(n²) der einfachen Sortierverfahren.
WENN laenge(liste) <= 1 DANN
GIB ZURÜCK liste // Basisfall
ENDE WENN
mitte = laenge(liste) / 2
links = mergeSort(liste[1..mitte]) // rekursiv
rechts = mergeSort(liste[mitte+1..ende])
GIB ZURÜCK merge(links, rechts)
ENDE FUNKTION
FUNKTION merge(a, b):
ergebnis = []
SOLANGE a nicht leer UND b nicht leer
WENN a[1] <= b[1] DANN
ergebnis.anhaengen(a.nehmeErstes())
SONST
ergebnis.anhaengen(b.nehmeErstes())
ENDE WENN
ENDE SOLANGE
ergebnis.anhaengen(rest von a und b)
GIB ZURÜCK ergebnis
ENDE FUNKTION
6) Komplexitäts-Vergleich aller vier
Wie gut sind die Algorithmen wirklich? Hier die Komplexitäten aller besprochenen Verfahren plus zwei weiterer wichtiger Sortierer zum Vergleich (Quicksort und Heapsort, die nicht in dieser Lektion behandelt werden, aber in jedem Algorithmen-Lehrbuch vorkommen):
| Algorithmus | Best Case | Average | Worst Case | Speicher | Stabil |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ja |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | nein |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ja |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | nein |
7) Stabile vs. instabile Sortierung
Ein häufig übersehenes Kriterium: Stabilität. Ein Sortierverfahren ist stabil, wenn Elemente mit gleichem Sortier-Schlüssel ihre ursprüngliche Reihenfolge behalten. Klingt akademisch? Ist in der Praxis sehr relevant.
Beispiel: du hast eine Tabelle mit Personen, sortiert nach Vorname. Jetzt sortierst du sie nach Nachname. Bei einem stabilen Sortierverfahren bleiben Personen mit gleichem Nachnamen in alphabetischer Vorname-Reihenfolge. Bei einem instabilen Verfahren wird die Sub-Sortierung zerstört.
- Stabil: Bubble Sort, Insertion Sort, Merge Sort
- Instabil: Selection Sort (in der naiven Variante), Quicksort, Heapsort
In der Praxis verwenden die meisten Programmiersprachen stabile Sortierungen als Standard. Java's Collections.sort() nutzt Timsort (eine Mischung aus Merge Sort und Insertion Sort). Python's sorted() ebenfalls Timsort. C++'s std::sort ist instabil (oft Introsort), aber es gibt std::stable_sort als stabile Alternative.
8) In-Place vs. Out-of-Place
Ein weiteres Unterscheidungsmerkmal: braucht der Algorithmus zusätzlichen Speicher (über die Eingabe-Liste hinaus)?
- In-Place (O(1) extra): Bubble, Selection, Insertion. Sortieren direkt im selben Array, brauchen nur etwas Platz für die Tausch-Variable. Speichersparend.
- Out-of-Place (O(n) extra): Merge Sort. Braucht ein Hilfsarray gleicher Größe zum Mergen. Bei sehr großen Daten (z.B. Sortierung auf Festplatte) kann das ein Problem sein.
Wenn der Speicher knapp ist – etwa auf embedded Systemen oder bei sehr großen Datensätzen – wird in-place bevorzugt. Heapsort ist ein Beispiel für einen in-place-Algorithmus mit O(n log n) Performance, kombiniert also beide Vorteile.
9) Wann nehme ich welchen Algorithmus?
In der Praxis musst du fast nie selbst sortieren – die Bibliothek deiner Programmiersprache hat das eingebaut, und besser. Aber für IHK-Klausuren und das algorithmische Verständnis hier ein paar Faustregeln:
- Kleine Liste (unter ~50 Elemente): Insertion Sort. Einfach, schnell genug, oft schneller als O(n log n) wegen geringer Konstanten.
- Fast sortierte Liste: Insertion Sort. Linear O(n) im besten Fall – andere Algorithmen sind hier oft langsamer.
- Große Liste, allgemein: Merge Sort oder Quicksort. Beide O(n log n) im Durchschnitt.
- Stabilität wichtig: Merge Sort (oder Timsort als hybrider Ansatz).
- Speicher knapp: Heapsort. In-Place und garantiert O(n log n).
- Externe Sortierung (Daten passen nicht in RAM): Merge Sort. Lässt sich gut auf Festplatte aufteilen und mergen.
- In der echten Welt: die Standard-Bibliothek deiner Sprache (Timsort in Java/Python, Introsort in C++). Selten selbst implementieren!
10) Klausur-Tipps zum Sortieren
Was wird in IHK-Aufgaben zum Thema Sortieren typischerweise gefragt? Hier die häufigsten Aufgabentypen:
- „Sortieren Sie die Liste [...] mit Bubble Sort und zeigen Sie den Zustand nach jedem Durchgang." Hier wichtig: pro Durchgang einen Zustand der Liste. Vorsichtig sein, ob „Durchgang" einen kompletten Außenschleifen-Lauf oder jeden einzelnen Tausch meint.
- „Wie viele Vergleiche braucht Algorithmus X im schlimmsten Fall?" Bubble/Insertion: ungefähr n(n-1)/2 ≈ n²/2. Selection: genau n(n-1)/2. Merge: n · log₂(n).
- „Welcher Sortier-Algorithmus ist stabil?" Bubble, Insertion, Merge → stabil. Selection (naiv), Quicksort, Heapsort → instabil.
- „Erklären Sie das Teile-und-Herrsche-Prinzip am Beispiel von Merge Sort." Drei Phasen: Teilen (rekursiv halbieren), Lösen (Basisfall: 1 Element), Zusammenführen (zwei sortierte Hälften mergen).
Zusammenfassung
Vier wichtige Sortier-Algorithmen. Die ersten drei sind einfach, aber langsam (O(n²)): Bubble Sort (Nachbarn vergleichen und tauschen), Selection Sort (Minimum suchen und nach vorne tauschen), Insertion Sort (in den sortierten Anfangsbereich einsortieren). Merge Sort ist deutlich schneller (O(n log n)) durch Teile-und-Herrsche: rekursiv halbieren bis auf Einzelelemente, dann paarweise sortiert zusammenführen. Wichtige Kriterien neben Geschwindigkeit: Stabilität (Reihenfolge gleicher Elemente erhalten – wichtig bei Mehrfach-Sortierung), Speicherbedarf (in-place mit O(1) vs. out-of-place mit O(n) extra), Best/Average/Worst Case. Untere Schranke für vergleichsbasierte Sortierung: O(n log n). Faustregeln: Insertion Sort für kleine oder fast sortierte Listen, Merge Sort für stabile O(n log n) Sortierung, Heapsort für in-place O(n log n), Quicksort für durchschnittlich schnellste Sortierung. In der Praxis: Standard-Bibliotheken nutzen meist Timsort (hybride Mischung). Eng verwandt sind Rekursion (Merge Sort), binäre Suche (braucht sortierte Daten) und natürlich die O-Notation – die nächste Lektion gibt dir das Vokabular zur Beschreibung von Laufzeit-Komplexität, das du in dieser Lektion implizit schon benutzt hast.