Sortierungen

Sortierungen sind Verfahren, die die Reihenfolge einer Sequenz von Elementen nach einer festgelegten Ordnung bestimmen oder verändern. Übliche Ordnungen sind numerisch, lexikografisch oder benutzerdefiniert.

Ziele sind die Vereinfachung von Suchen, das Zusammenführen von Datensätzen, das Entfernen von Duplikaten sowie die effiziente Darstellung von Daten. Gut sortierte Daten ermöglichen auch Stabilität bei weiteren Operationen wie Zusammenführung oder Selektion.

Sortierverfahren lassen sich grob in vergleichsbasierte und nicht vergleichbare Sortierung einteilen. Vergleichsbasierte Sortierer wie Blasensortierung, Einfügesortierung, Auswahl, Quicksort, Mergesort und Heapsort entscheiden die Reihenfolge ausschließlich durch paarweise Vergleiche. Nicht vergleichbare Verfahren wie Counting Sort, Radix Sort oder Bucket Sort nutzen Eigenschaften der Schlüssel, zum Beispiel ganze Zahlen oder Ziffern.

Wichtige Eigenschaften sind Stabilität (gleiche Schlüssel behalten relative Reihenfolge) und der Speicherbedarf; manche Algorithmen arbeiten in-place (O(1) zusätzlichen Speicher), andere benötigen zusätzlichen Speicher.

Leistung: Die Laufzeit hängt vom Algorithmus und der Eingabe ab. Allgemein gilt: effiziente Allzwecksortierverfahren haben durchschnittliche und schlechte Fälle von O(n log n), während einfache Sortierverfahren O(n^2) kosten können. Raumkomplexität variiert.

Anwendungen und Entwicklungen: In der Praxis werden oft sortierbare Bibliotheksfunktionen eingesetzt; Timsort ist in vielen Sprachen verbreitet; externes Sortieren für sehr große Datenmengen; parallele Sortierverfahren nutzen Mehrkernprozessoren.