Sortieren

Sortieren bezeichnet das systematische Anordnen einer Folge von Elementen nach definierten Ordnungen, zum Beispiel aufsteigend oder absteigend. In der Informatik beschreibt Sorting den Prozess, bei dem eine Sequenz von Elementen mithilfe eines Sortierverfahrens in eine bestimmte Reihenfolge gebracht wird. Zentrale Aspekte sind das verwendete Ordnungskriterium (Schlüssel) sowie Eigenschaften des Verfahrens wie Stabilität und Speicherbedarf.

Vergleichsbasierte Sortieralgorithmen verwenden Paarvergleiche, um die Reihenfolge zu bestimmen. Typische Verfahren sind Quicksort, Mergesort, Heapsort, Einfügesort, Auswahl- und Bubblesort. Quicksort hat im Durchschnitt eine Laufzeit von O(n log n), kann im schlimmsten Fall auf O(n^2) degradieren. Mergesort liefert O(n log n) sicher, benötigt aber zusätzlichen Speicher. Heapsort arbeitet inplace und erreicht ebenfalls O(n log n). Nichtvergleichsbasierte Sortieralgorithmen wie Counting Sort, Radix Sort oder Bucket Sort können unter geeigneten Voraussetzungen bessere Grenzwerte erreichen, oft O(n) oder O(n log k).

Stabilität bedeutet, dass gleichwertige Schlüssel ihre relative Reihenfolge beibehalten. In-Place-Sortieralgorithmen verwenden wenig zusätzlichen Speicher, was in speicherlimitierten Umgebungen vorteilhaft ist. Externes Sortieren behandelt Sortieraufgaben, die größer sind als der verfügbare Hauptspeicher, typischerweise durch externe Merge-Strategien.

Sortieren findet breite Anwendungen: von kleinen Listen in Programmen bis hin zu großen Datenbeständen in Datenbanken, Suchsystemen und numerischen Anwendungen. Die Wahl des Algorithmus hängt von Datenmenge, Speicherlimit, Stabilitätsbedarf und gewünschten Laufzeiteigenschaften ab.