Sortieralgorithmen — Wie Computer Ordnung schaffen

Einführung

Sortieren ist eine der häufigsten Aufgaben, die Computer ausführen. Eine Playlist nach Datum ordnen, Suchergebnisse nach Relevanz sortieren, Datenbankeinträge alphabetisch anzeigen — hinter all dem steckt ein Sortieralgorithmus.

Klingt nach einem gelösten Problem? Ist es in gewisser Weise auch — aber das „Wie” macht einen enormen Unterschied. Ein schlechter Algorithmus braucht bei 10.000 Elementen Sekunden. Ein guter braucht Millisekunden. Bei Millionen Elementen entscheidet das über die Praxis­tauglichkeit einer Anwendung.

In dieser Lektion lernst du vier Sortierverfahren kennen — vom intuitiven, aber langsamen Bubblesort bis zum effizienten Mergesort — und verstehst, warum der Unterschied enorm ist.

Grundidee

Alle vergleichsbasierten Sortieralgorithmen arbeiten nach demselben Grundprinzip: Vergleiche zwei Elemente und entscheide, welches nach vorne gehört. Wiederhole das so oft, bis alles in der richtigen Reihenfolge ist.

Der Unterschied liegt darin, wie oft und welche Elemente verglichen werden — und wie clever der Algorithmus dabei vorgeht.

Einfache Verfahren (Bubblesort, Selectionsort) sind leicht verständlich, aber ineffizient. Schlaue Verfahren (Mergesort, Quicksort) sind komplexer, aber dramatisch schneller.

Erklärung

Bubblesort

Idee: Gehe die Liste von links nach rechts durch. Vergleiche immer zwei benachbarte Elemente. Sind sie in der falschen Reihenfolge, tausche sie. Wiederhole so oft, bis keine Tausche mehr nötig sind.

Beispiel: [5, 3, 8, 1]

• Durchlauf 1: Vergleiche 5 und 3 → tausche: [3, 5, 8, 1]. Vergleiche 5 und 8 → ok. Vergleiche 8 und 1 → tausche: [3, 5, 1, 8]. Größtes Element „blubbert” nach rechts.
• Durchlauf 2: [3, 1, 5, 8].
• Durchlauf 3: [1, 3, 5, 8]. Fertig.

Laufzeit: Im schlechtesten Fall n Durchläufe × n Vergleiche = O(n²).

Bei 1.000 Elementen: ~1 Million Vergleiche. Bei 10.000 Elementen: ~100 Millionen. Das wird schnell zu langsam.

Selectionsort

Idee: Suche das kleinste Element der gesamten Liste, setze es an den Anfang. Suche dann das kleinste in der Restliste, setze es an die zweite Stelle. Und so weiter.

Ebenfalls O(n²) — aber etwas weniger Tauschoperationen als Bubblesort.

Mergesort

Mergesort ist deutlich cleverer. Es nutzt das Teile-und-Herrsche-Prinzip (Divide and Conquer).

Idee:

1. Teile die Liste in zwei gleich große Hälften.
2. Sortiere jede Hälfte rekursiv (mit Mergesort).
3. Mische (Merge) die zwei sortierten Hälften zu einer sortierten Liste.

Beispiel: [5, 3, 8, 1]

1. Teile: [5, 3] und [8, 1]
2. Sortiere: [3, 5] und [1, 8]
3. Mische: Vergleiche jeweils das kleinste Element beider Hälften. 1 < 3 → nimm 1. 3 < 8 → nimm 3. 5 < 8 → nimm 5. Dann 8. Ergebnis: [1, 3, 5, 8].

Laufzeit: Das Teilen braucht O(log n) Ebenen (halbe die Liste so lange, bis Einzel­elemente übrig sind). Das Mischen auf jeder Ebene braucht O(n). Gesamt: O(n log n).

Warum ist das so viel besser?

n	O(n²)	O(n log n)
100	10.000	700
10.000	100.000.000	133.000
1.000.000	1.000.000.000.000	20.000.000

Der Unterschied ist bei großen Datenmengen dramatisch.

Quicksort

Quicksort ist in der Praxis oft sogar schneller als Mergesort, obwohl es im schlechtesten Fall O(n²) hat.

Idee:

1. Wähle ein Pivot-Element (z. B. das letzte Element der Liste).
2. Teile die Liste in zwei Gruppen: Elemente kleiner als Pivot, Elemente größer als Pivot.
3. Wende Quicksort rekursiv auf beide Gruppen an.

Der Witz: Die Teilung passiert so, dass kein Merge-Schritt nötig ist. Im Durchschnitt (bei guter Pivot-Wahl) O(n log n) — aber im Worst Case (sortierte Liste + schlechte Pivot-Wahl) O(n²).

In der Praxis verwendet man gute Heuristiken für die Pivot-Wahl. Deshalb ist Quicksort trotz des schlechten Worst Case meistens die Wahl in realen Systemen.

Stabiles Sortieren

Ein Sortieralgorithmus heißt stabil, wenn Elemente mit gleichen Werten in ihrer ursprünglichen Reihenfolge bleiben. Mergesort ist stabil, Quicksort in der Standardversion nicht.

Warum wichtig? Wenn du eine Liste nach Nachnamen sortierst, die vorher nach Vornamen sortiert war — dann willst du, dass Personen mit demselben Nachnamen nach wie vor nach Vorname geordnet sind. Nur stabile Algorithmen garantieren das.

Wann welchen Algorithmus?

Situation	Empfehlung
Kleine Listen (< 50 Elemente)	Insertionsort oder einfache Verfahren
Allgemeiner Einsatz	Quicksort (meistens schnell)
Stabilität nötig	Mergesort
Garantierte O(n log n) Worst-Case	Mergesort oder Heapsort

Moderne Programmiersprachen verwenden in der Praxis hybride Verfahren: Python nutzt Timsort (Mischung aus Mergesort und Insertionsort), Java Arrays.sort() ebenfalls.

Beispiel aus dem Alltag

Playlist sortieren:

Wenn du eine Musikbibliothek mit 50.000 Songs nach Titel sortierst, macht Bubblesort ~2,5 Milliarden Vergleiche. Mergesort: ~850.000. Der Unterschied ist der Grund, warum Apps reaktionsschnell sind — oder nicht.

Datenbankabfragen:

Datenbanken wie PostgreSQL oder MySQL sortieren Ergebnisse intern bei jeder Abfrage. Die Effizienz des Sortieralgorithmus entscheidet darüber, wie schnell Abfragen zurückkommen — besonders bei Millionen von Einträgen.

Suchmaschinenranking:

Google sortiert Milliarden von Seiten nach Relevanz für deine Anfrage. Das passiert in Millisekunden — möglich durch eine Kombination aus Caching, vorberechneten Indizes und effizienten Sortierverfahren im Hintergrund.

Anwendung

Führe Bubblesort manuell auf der folgenden Liste aus und notiere jeden Schritt:

[7, 2, 9, 4, 1]

1. Wie viele Vergleiche sind insgesamt nötig?
2. Wie viele Tauschoperationen passieren?
3. Vergleiche: Wie viele Schritte würde Mergesort auf derselben Liste brauchen?

Überlege dann: Welchen Algorithmus würdest du verwenden, wenn du eine Liste von 10 Millionen Kundennamen alphabetisch sortieren müsstest — und warum?

Typische Fehler

Bubblesort als „gut genug” betrachten: Für Schulaufgaben mit 10 Elementen ist das egal. In echten Anwendungen ist O(n²) bei großen Daten oft indiskutabel langsam.

O(n log n) als „immer optimal” sehen: Es gibt Spezialprobleme, wo bessere Komplexität möglich ist — zum Beispiel Counting Sort in O(n + k) für kleine Integer-Bereiche. Aber Vergleichsbasiertes Sortieren kann theoretisch nicht besser als O(n log n) sein (das ist beweisbar).

Stabilität ignorieren: Nicht jeder Anwendungsfall braucht Stabilität, aber wenn doch, muss man daran denken.

Rekursion für Mergesort vergessen: Mergesort ist rekursiv und braucht Stapelspeicher (Call Stack) proportional zu O(log n). Bei extrem großen Listen kann das relevant werden.

Zusammenfassung

• Bubblesort und Selectionsort sind einfach, aber langsam: O(n²) — bei großen Listen praktisch untauglich
• Mergesort nutzt Teile-und-Herrsche: Teile, sortiere rekursiv, mische — Ergebnis: O(n log n)
• Quicksort ist in der Praxis oft der schnellste, aber im Worst Case O(n²); bei guter Pivot-Wahl bleibt es durchschnittlich bei O(n log n)
• Der Unterschied zwischen O(n²) und O(n log n) ist bei 1 Mio. Elementen der Faktor 50.000
• Stabiles Sortieren erhält die relative Reihenfolge gleicher Elemente — wichtig bei mehrkriteriellen Sortierungen
• Moderne Sprachen nutzen hybride Verfahren wie Timsort, die Mergesort und Insertionsort kombinieren

Quiz

Frage 1: Erkläre das Grundprinzip von Mergesort in drei Schritten.

Frage 2: Was bedeutet O(n log n) — und warum ist das so viel besser als O(n²)?

Frage 3: Was ist stabiles Sortieren — und wann ist es wichtig?

Frage 4: Warum ist Quicksort in der Praxis oft schneller als Mergesort, obwohl es im Worst Case O(n²) hat?