Sortierung

Sortierung ist der Prozess der Anordnung von Objekten nach einem festgelegten Kriterium, wobei die Reihefolge in der Regel entweder aufsteigend oder absteigend erfolgt. In vielen Kontexten dient sie der Vergleichbarkeit, Durchsuchbarkeit und Effizienz von nachfolgenden Operationen.

Kriterien können numerische Werte, Zeichenketten oder benutzerdefinierte Schlüssel sein. Eine Sortierung kann stabil sein, das heißt, gleiche Schlüssel behalten ihre relative Reihenfolge; oder instabil, bei der diese Reihenfolge sich ändern kann.

In der Informatik unterscheidet man vergleichsbasierte Sortieralgorithmen (die Paarvergleiche nutzen) von nicht vergleichbaren Sortierverfahren. Bekannte Algorithmen sind Quicksort (durchschnittliche Komplexität O(n log n), schlechtester Fall O(n^2)), Mergesort (O(n log n), stabil), Heapsort (O(n log n), in der Regel instabil), Insertion Sort (O(n^2), gut für kleine oder fast sortierte Daten). Nichtvergleichbare Sortierer wie Counting Sort oder Radix Sort arbeiten je nach Schlüsseltyp in linearem Zeitraum, sind aber an bestimmte Voraussetzungen gebunden. Externe Sortierung wird eingesetzt, wenn die Datenmenge zu groß ist, um den Hauptspeicher zu fassen, oft mit Multiway-Mergesort.

Die Wahl eines Sortierverfahrens hängt von Faktoren ab wie Datenmenge, Datentyp, Stabilitätsbedarf, Speicherbegrenzungen und Anpassung an vorhandene Strukturen (z. B. Spalten in Tabellen).

Sortierung bildet eine grundlegende Vorverarbeitung in vielen Bereichen: Datenbanken, Suchfunktionen, Analytik sowie in Algorithmenbausteinen wie Gruppierung, Medianberechnung und Indexierung.