Sortieralgorithmen bringen eine Menge von Elementen in eine definierte Reihenfolge, zum Beispiel Zahlen aufsteigend oder Namen alphabetisch. Sortierte Daten sind die Grundlage vieler Anwendungen: Schnellsuche, Duplikaterkennung, Ranglisten oder die Aufbereitung von Berichten. Ein Algorithmus beschreibt dabei exakt, nach welchen Schritten die Sortierung abläuft.
Wichtige Eigenschaften
- Stabilität: Ein sortieralgorithmus ist stabil, wenn gleiche Elemente ihre ursprüngliche Reihenfolge behalten. Das ist etwa beim Sortieren nach mehreren Schlüsseln wichtig.
- In-place: Ein Verfahren sortiert in-place, wenn es das vorhandene Array direkt umordnet und kaum zusätzlichen Speicher braucht.
- Laufzeit: Die Komplexität gibt an, wie schnell ein Verfahren wächst. Einfache Verfahren brauchen im Schnitt O(n²) Vergleiche, effiziente Verfahren O(n log n) — bei großen Datenmengen ist der Unterschied enorm.
Einfache Verfahren O(n²)
- Bubble Sort: Benachbarte Elemente werden verglichen und bei falscher Reihenfolge getauscht, bis alles sortiert ist. Einfach zu verstehen, aber langsam.
- Selection Sort: Sucht jeweils das kleinste Element und stellt es an die nächste Position.
- Insertion Sort: Nimmt Element für Element und fügt es an der richtigen Stelle in den bereits sortierten Teil ein. Bei fast sortierten Daten sehr schnell.
Effiziente Verfahren O(n log n)
- Merge Sort: Teilt die Liste rekursiv in Hälften, sortiert diese und verschmilzt sie anschließend. Stabil, braucht aber zusätzlichen Speicher.
- Quick Sort: Wählt ein Pivot-Element und teilt die Daten in kleinere und größere Elemente auf, die dann rekursiv sortiert werden. In der Praxis oft das schnellste Verfahren.
- Heap Sort: Baut aus den Daten einen Heap auf und entnimmt wiederholt das größte Element. Der Heap ist ein spezieller Binärbaum.
Merge Sort und Quick Sort arbeiten mit Rekursion: Sie rufen sich selbst auf immer kleineren Teilmengen auf. Die Kontrollstrukturen Schleife und bedingte Anweisung steuern die Vergleiche und Vertauschungen.
Spezielle Verfahren
Für besondere Daten gibt es Verfahren wie Counting Sort oder Radix Sort, die ohne Vergleiche auskommen und bei passenden Zahlenbereichen in linearer Zeit arbeiten. Sie sortieren dagegen nur ganzzahlige oder ähnlich strukturierte Datentypen.
Praxis
In der Praxis ruft man selten einen eigenen Algorithmus auf: Standardbibliotheken liefern fertige, optimierte Sortierfunktionen für Listen, Arrays und Tabellen. Wer die Verfahren trotzdem kennt, versteht, warum große Datenmengen teils augenblicklich, teils sehr langsam sortiert werden — und wählt die passende Datenstruktur wie Baum oder Heap bewusst aus.