Wikipedia · einfach zusammengefasst · Stand
Sortierverfahren
Unter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren.
Inhalt5 Abschnitte
Grundlagen und wichtige Eigenschaften
Ein Sortierverfahren ist in der Informatik ein Algorithmus, der ein Tupel, im Allgemeinen ein Array, in eine geordnete Reihenfolge bringt. Voraussetzung ist eine strenge schwache Ordnung („kleiner-gleich“) auf der Menge der Elemente, zum Beispiel die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Auch eine starke Ordnung („kleiner“) erfüllt diese Voraussetzung.
Sortierverfahren unterscheiden sich vor allem hinsichtlich ihrer Zeitkomplexität, also der Anzahl notwendiger Operationen, und ihrer Platzkomplexität, also des zusätzlichen Speicherplatzes neben dem Eingabe-Array. Zur Darstellung wird meist die Landau-Notation verwendet, etwa Θ(n · log(n)), O oder Ω. Je nach anfänglicher Anordnung der Daten werden Best Case (günstigste Vorsortierung), Average Case (Normalfall) und Worst Case (ungünstigste Anordnung) unterschieden. Zusätzlich können langsamer Zugriff auf extern liegende Daten oder begrenzter Arbeitsspeicher die praktische Auswahl beeinflussen.
Ein stabiles Sortierverfahren erhält die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind. Wird beispielsweise eine nach Nachnamen geordnete Mitarbeiterliste anschließend nach Alter sortiert, bleibt bei einem stabilen Verfahren die Nachnamen-Reihenfolge unter gleichaltrigen Mitarbeitern erhalten. Instabile Verfahren garantieren dies nicht.
In-place- beziehungsweise in-situ-Verfahren benötigen zusätzlichen Speicher, der unabhängig von der Anzahl n der Elemente ist und meist konstant sowie gering ausfällt. Out-of-place- oder ex-situ-Verfahren benötigen dagegen zusätzlichen Speicherplatz, der von n abhängt. Natürliche Sortierverfahren arbeiten bei vorsortierten Daten schneller als bei unsortierten. Hängt der Kontrollfluss von den Daten ab, heißt der Algorithmus adaptiv; nicht von den Eingabedaten abhängige Verfahren heißen nicht-adaptiv und sind daher besonders für Hardware-Implementierungen interessant. Manuelles Sortieren, etwa von Karteikarten, sowie elektromechanisches Sortieren, etwa von Lochkarten, entsprechen meist softwarebasierten Sortierverfahren oder Mischtypen.
Vergleichsbasierte Verfahren
Vergleichsbasierte Sortierverfahren ordnen Elemente durch paarweise Vergleiche. Dabei wird geprüft, ob ein Element kleiner, größer oder gleich dem anderen ist; häufig werden nur die beiden Ergebnisse „kleiner“ und „nicht kleiner“ unterschieden. Bei der Komplexitätsanalyse gilt der Aufwand für einen Elementvergleich als konstant.
Die Tabelle des Artikels nennt unter anderem folgende Ergebnisse: Höhen-balanciertes Binary Tree Sort benötigt im Best, Average und Worst Case jeweils Θ(n · log(n)), ist instabil und braucht Θ(n) zusätzlichen Speicher. Nicht höhen-balanciertes Binary Tree Sort ist im Best und Average Case Θ(n · log(n)), im Worst Case Θ(n²), stabil und benötigt Θ(n) Speicher. Bubblesort, Gnomesort und Insertionsort sind stabil, benötigen im Best Case Θ(n), im Average und Worst Case Θ(n²) und arbeiten ohne zusätzlichen Speicher. Shakersort (Cocktailsort) hat dieselben Komplexitäten und ist ebenfalls stabil. Combsort ist instabil, erreicht Θ(n · log(n)) im Best Case und O(n²) im Average und Worst Case.
Heapsort, Introsort und Merge Insertion haben in allen drei Fällen Θ(n · log(n)); Heapsort und Introsort sind instabil, Merge Insertion ist stabil. Mergesort ist in allen Fällen Θ(n · log(n)) und stabil. Auf verketteten Listen kann Mergesort in-place implementiert werden; übliche Array-Implementierungen benötigen Θ(n) zusätzlichen Speicher. Es gibt auch eine in-place-Variante für Arrays, deren Zeitkomplexität als n · (log n) · (log n) angegeben wird. Natural Mergesort nutzt vorhandene Ordnung: Im Best Case Θ(n), sonst im Average und Worst Case Θ(n · log(n)); es ist stabil.
Quicksort benötigt im Best und Average Case Θ(n · log(n)), im Worst Case Θ(n²), ist instabil und braucht Θ(log(n)) zusätzlichen Speicher; übliche Implementierungen benötigen meist mehr. Samplesort hat im Best und Average Case Θ(n · log(n)), im Worst Case Θ(n²), ist instabil und benötigt Θ(n) Speicher. Selectionsort ist in allen Fällen Θ(n²), instabil und kommt ohne zusätzlichen Speicher aus. Shellsort wird in allen drei Fällen mit O(n · log(n)²) angegeben und ist instabil. Smoothsort ist instabil und benötigt Θ(n) im Best sowie Θ(n · log(n)) im Average und Worst Case.
Stoogesort ist instabil und wird in allen Fällen mit Ω(n^{2,7}) angegeben. Swap-Sort benötigt in allen Fällen Θ(n²); seine Stabilität ist in der Tabelle mit „–“ angegeben. Timsort ist stabil, hat Θ(n) im Best Case sowie Θ(n · log(n)) im Average und Worst Case und benötigt Θ(n) zusätzlichen Speicher. Bogosort ist instabil, hat Θ(n) im Best Case, O(n · n!) im Average Case, eine unbegrenzte Laufzeit im Worst Case und keinen angegebenen zusätzlichen Speicherbedarf. Slowsort ist instabil und wird in allen Fällen mit Ω(n^{log(n)/(2+ε)}) angegeben.
Nicht-vergleichsbasiertes und hybrides Sortieren
Nicht-vergleichsbasierte Verfahren vergleichen die zu sortierenden Objekte nicht untereinander auf „kleiner“, „größer“ oder „gleich“. Bei entsprechend konditionierten Eingaben kann ihre Laufzeit nur linear mit der Anzahl n der Elemente wachsen. Bei großen Datenmengen können sie vergleichsbasierten Verfahren überlegen sein, sofern ihr zusätzlicher Speicherbedarf und ihre Voraussetzungen erfüllt sind.
Sie eignen sich unmittelbar nur für numerische Datentypen oder für Datentypen, die mit vertretbarem Aufwand auf Zahlenwerte gleicher Anordnung abgebildet werden können. Dabei wird vorausgesetzt, dass die Schlüssellänge beschränkt ist und der Schlüssel in konstanter Zeit verarbeitet werden kann. Die geringere Abhängigkeit von der Elementanzahl wird durch eine weitere zeitliche Abhängigkeitsgröße erkauft, meist die Schlüssellänge oder die Anzahl möglicher Schlüsselwerte, häufig verbunden mit erheblichem zusätzlichem Speicherbedarf. In der Tabelle bezeichnet n die Anzahl der Elemente, k die Anzahl möglicher Werte und l die Anzahl der Stellen des längsten Schlüssels.
Bucketsort und Countingsort sind stabil, haben die Zeitkomplexität O(n+k) und benötigen O(n+k) zusätzlichen Speicher. Radixsort ist stabil, benötigt O(n · l) Zeit und O(n) zusätzlichen Speicher. MSD Radixsort benötigt ebenfalls O(n · l) Zeit, ist aber instabil und kann in-place mit O(1) zusätzlichem Speicher arbeiten. Flashsort ist instabil, hat je nach Fall eine Laufzeit von O(n) bis O(n²) und benötigt O(1) zusätzlichen Speicher.
Hybridsort verbindet vergleichsbasiertes und nicht-vergleichsbasiertes Sortieren in zwei aufeinanderfolgenden Phasen.
Sortierung nach Beziehungen und indirektes Sortieren
Bei einer topologischen Sortierung werden Objekte nicht nach Eigenschaften, sondern nach paarweisen Beziehungen geordnet. Ein typisches Beispiel ist eine Menge von Aufgaben, bei der manche Aufgaben zwingend vor anderen erledigt werden müssen, während die Reihenfolge anderer Aufgaben frei ist. Die Laufzeit topologischer Sortieralgorithmen hängt von der Anzahl der Beziehungen ab.
Eine topologische Sortierung ist nicht möglich, wenn gegenseitige, also zyklische Abhängigkeiten bestehen. Außerdem muss sie nicht eindeutig sein. Sind die Beziehungen vollständig und ist für jedes Paar von Objekten eine Abhängigkeit vorgegeben, geht die topologische Sortierung in eine gewöhnliche Sortierung über.
Indirektes Sortieren wird eingesetzt, wenn das eigentliche Umstellen der Daten aufwendig ist. Dazu wird ein zusätzliches Array mit Speicher proportional zur Elementanzahl verwendet, beispielsweise mit einem Zeiger auf jedes Element oder dessen Indexnummer im Basis-Array. Dieses Index-Array wird sortiert und bildet anschließend einen nach dem Vergleichskriterium geordneten Index. Sollen auch die ursprünglichen Daten in die richtige Reihenfolge gebracht werden, ist dafür zusätzlich ein Aufwand von Θ(n) erforderlich. Ist bereits der wahlfreie Zugriff auf die Elemente teuer, können auch die für den Sortierschlüssel relevanten Datenkomponenten oder der Sortierschlüssel selbst in den Index übernommen werden; dadurch steigt der zusätzliche Speicherbedarf.
Untere Schranke und praktische Anwendungen
Für vergleichsbasierte Sortierverfahren gilt eine fundamentale untere Schranke: Kein solches Verfahren kann schneller als Ω(n · log(n)) sein. Im Entscheidungsbaum B eines Sortieralgorithmus für die Zahlenfolge X=(x₁,…,xₙ) muss jede der n! möglichen Permutationen durch mindestens ein Blatt repräsentiert werden. Der Baum besitzt daher mindestens n! Blätter. Die maximale und die mittlere Tiefe eines Blattes sind in einem Entscheidungsbaum mit n! Blättern mindestens log(n!). Mit der Abschätzung n! ≥ (n/2)^{n/2} folgt log(n!) ≥ (n/2) · log(n/2) = Ω(n · log(n)).
Für einen Binärbaum mit k Blättern lässt sich außerdem zeigen, dass die maximale und die mittlere Tiefe mindestens log(k) betragen. Haben die beiden Teilbäume T₁ und T₂ jeweils k₁ beziehungsweise k₂ Blätter, gilt k₁<k, k₂<k und k₁+k₂=k. Für die mittlere Tiefe ergibt sich:
mittlere Tiefe(B) = (k₁/k) · (mittlere Tiefe(T₁)+1) + (k₂/k) · (mittlere Tiefe(T₂)+1) ≥ (k₁/k) · (log(k₁)+1) + (k₂/k) · (log(k₂)+1).
Das Minimum liegt bei k₁=k₂=k/2. Dann folgt mittlere Tiefe(B) ≥ (1/k) · ((k/2) · log(k) + (k/2) · log(k)) = log(k). Dies widerspricht der Annahme einer geringeren Tiefe und beweist die Schranke.
Beim Sortieren natürlicher Sprache, etwa von Nachnamen, entstehen besondere Probleme. Anfangsbuchstaben kommen unterschiedlich häufig vor; in Deutschland ist X beispielsweise seltener als B. Gleich große Buckets beim Bucketsort nach Anfangsbuchstaben werden deshalb unterschiedlich gefüllt. Außerdem muss eine konsistente Regel gelten, wenn ein kürzeres Wort Präfix eines längeren ist, etwa „Li“ vor „Liebig“. Sprachspezifische Vergleichsregeln können durch Funktionen der Softwarebibliothek locale.py berücksichtigt werden, die abhängig von der konfigurierten Sprache Vergleiche ermöglichen oder eine geeignete Sortier-Zeichenkette erzeugen.
Für eine Sortierung nach mehreren Spaltenwerten in einer relationalen Datenbank, etwa mit SQL „ORDER BY Alter, Hausnummer“, können die Werte verschiedener Spalten zu einem Binärwert zusammengefügt und dieser als Ganzzahl sowie als Sortierschlüssel verwendet werden. In einer Software können mehrere Sortierverfahren nebeneinander eingesetzt werden; DuckDB verwendet Vergesort, Ska Sort und Pattern-defeating quicksort.
