Sortierverfahren

Unter e​inem Sortierverfahren versteht m​an in d​er Informatik e​inen Algorithmus, d​er dazu dient, e​in Tupel (i. Allg. e​in Array) z​u sortieren. Voraussetzung ist, d​ass auf d​er Menge d​er Elemente e​ine strenge schwache Ordnung definiert i​st („kleiner-gleich“), z. B. d​ie lexikographische Ordnung v​on Zeichenketten o​der die numerische Ordnung v​on Zahlen.

Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten bezüglich der Zeitkomplexität (Anzahl der nötigen Operationen) sowie der Platzkomplexität (zusätzlich zum Eingabe-Array benötigter weiterer Speicherplatz). Die Komplexität eines Algorithmus wird üblicherweise in der Landau-Notation dargestellt (s. u. Ausdrücke wie ${\displaystyle \Theta (n\cdot \log(n))}$). Die Zeitkomplexität hängt bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bei günstigster „Vorsortierung“), Average Case (Normalfall) und Worst Case (schlechtester Fall ~ die Werte sind „maximal ungünstig vorgeordnet“). Häufig sind zusätzliche Faktoren zu beachten, die Einfluss auf Zeit- oder Platzkomplexität haben, zum Beispiel langsamer Zugriff auf extern liegende Daten, begrenzte Größe des Arbeitsspeichers oder ähnliches.

Man unterscheidet z​udem zwischen stabilen u​nd instabilen Sortierverfahren. Stabile Sortierverfahren s​ind solche, d​ie die relative Reihenfolge v​on Elementen, d​ie bezüglich d​er Ordnung äquivalent sind, n​icht verändern, während instabile Sortierverfahren d​ies nicht garantieren. Ist beispielsweise d​ie Mitarbeiterliste e​iner Firma n​ach Nachname geordnet u​nd wird anschließend n​ach Alter (in Jahren) sortiert, s​o bleibt d​ie (Nachnamen-)Reihenfolge u​nter gleichaltrigen Mitarbeitern b​ei einem stabilen Sortierverfahren bestehen.

Zudem unterscheidet m​an zwischen Sortierverfahren, d​ie in-place (auch in situ) arbeiten, d. h. d​er zusätzliche Speicherbedarf i​st unabhängig v​on der Anzahl d​er zu sortierenden Elemente (also konstant u​nd meist gering), u​nd solchen, b​ei denen e​r abhängig i​st (out-of-place o​der ex situ).

Und m​an unterscheidet a​uch zwischen natürlichen Sortierverfahren, d​ie bei vorsortierten Daten schneller arbeiten a​ls bei unsortierten Daten, u​nd solchen, d​ie es n​icht tun. Algorithmen, b​ei denen d​er Kontrollfluss v​on den Daten abhängt, n​ennt man adaptiv u​nd dementsprechend Sortierverfahren, d​ie nicht v​on den Eingabedaten abhängen, nicht-adaptiv. Nicht-adaptive Algorithmen s​ind demnach besonders interessant für Hardware-Implementierungen.

Manuelles Sortieren (etwa v​on Karteikarten) s​owie elektro-mechanische Sortierverfahren (z. B. für Lochkarten) entsprechen m​eist einem d​er hier beschriebenen softwarebasierten Sortierverfahren, o​der Mischtypen.

Vergleichsbasiertes Sortieren

Allgemeine Verfahren basieren a​uf dem paarweisen Vergleich d​er zu sortierenden Elemente, o​b das e​ine Element „kleiner“ als, „größer“ a​ls oder „gleich(groß)“ w​ie das andere Element ist. Bei d​er Komplexitätsanalyse w​ird davon ausgegangen, d​ass der Aufwand z​um Vergleich zweier Elemente konstant ist.

Sortierverfahren	Günstigster Fall („Best-Case“)	Mittlerer Fall („Average-Case“)	Ungünstigster Fall („Worst-Case“)	Stabil	Zusätzlicher Speicherbedarf
Binary Tree Sort (höhen-balanciert)	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	ja[1]	${\displaystyle \Theta (n)}$
Binary Tree Sort	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n^{2})}$	ja[1]	${\displaystyle \Theta (n)}$
Bubblesort	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	ja	–
Combsort	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle {\mathcal {O}}(n^{2})}$	${\displaystyle {\mathcal {O}}(n^{2})}$	nein	–
Gnomesort	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	ja	–
Heapsort	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	nein	–
Insertionsort	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	ja	–
Introsort	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	nein	–
Merge Insertion	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$[2]	${\displaystyle \Theta (n\cdot \log(n))}$	ja	–
Mergesort	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	ja	Implementierung auf verketteter Liste: in-place übliche Implementierungen (auf Array): ${\displaystyle \Theta (n)}$ Es gibt in-place auf Array, jedoch dann Zeitkomplex. = n * (log n) * (log n) .
Natural Mergesort	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	ja	–
Quicksort	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n^{2})}$	nein	${\displaystyle \Theta (\log(n))}$, übliche Implementierungen benötigen meist mehr
Selectionsort	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	nein	–
Shakersort (Cocktailsort)	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	ja	–
Shellsort	${\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}$[3]	${\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}$[3]	${\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}$[3]	nein	–
Smoothsort	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	nein	–
Stoogesort	${\displaystyle \Omega (n^{2,7})}$	${\displaystyle \Omega (n^{2,7})}$	${\displaystyle \Omega (n^{2,7})}$	nein	–
Swap-Sort	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	${\displaystyle \Theta (n^{2})}$	–	–
Timsort	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n\cdot \log(n))}$	${\displaystyle \Theta (n\cdot \log(n))}$	ja	–
Bogosort	${\displaystyle \Theta (n)}$	${\displaystyle {\mathcal {O}}(n\cdot n!)}$[4]	${\displaystyle {\mathcal {O}}(n\cdot n!)}$[4]	nein	–
Slowsort	${\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}$[5]	${\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}$[5]	${\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}$[5]	nein	–

1. Für die stabile Version s. die Bemerkung im Artikel Binary Tree Sort.
2. Florian Stober, Armin Weiß: On the Average Case of MergeInsertion. Abgerufen am 20. Januar 2022.
3. Für die (im Worst Case) beste bekannte Distanzfolge.
4. Erwartete Laufzeit.
5. Für ein beliebiges ${\displaystyle \varepsilon >0}$, siehe Slowsort.

Nicht-vergleichsbasiertes Sortieren

Bei Sortierverfahren, die nicht auf Vergleichen beruhen, bei denen die zu sortierenden Objekte also nicht untereinander auf „kleiner“, „größer“ oder „gleich“ verglichen werden, kann bei entsprechend konditionierter Eingabe erreicht werden, dass die benötigte Zeit nur linear mit der Anzahl der zu sortierenden Elemente ansteigt. Bei großen Anzahlen zu sortierender Datensätze sind diese Algorithmen den vergleichsbasierten Verfahren überlegen, sofern sie (wegen des zusätzlichen Speicherbedarfs) angewendet werden können. Sie können allerdings nur für numerische Datentypen verwendet werden (oder unter der Bedingung, dass der Datentyp in annehmbarem Aufwand auf Zahlenwerte gleicher Anordnung abgebildet werden kann). Dabei wird implizit angenommen, dass die Länge des Schlüssels beschränkt ist, so dass seine Verwertung in konstanter Zeit möglich ist. Das Senken der Zeitkomplexität von der Elementanzahl wird erkauft durch eine zusätzliche zeitliche Abhängigkeitsgröße (meist der Schlüssellänge oder der Anzahl möglicher Schlüsselwerte), oft auch durch erheblichen zusätzlichen Speicherbedarf.

Sortierverfahren	Zeit	Stabil	Zusätzlicher Speicherbedarf
Bucketsort	${\displaystyle {\mathcal {O}}\left(n+k\right)}$	ja	${\displaystyle {\mathcal {O}}\left(n+k\right)}$
Countingsort	${\displaystyle {\mathcal {O}}\left(n+k\right)}$	ja	${\displaystyle {\mathcal {O}}\left(n+k\right)}$
Radixsort	${\displaystyle {\mathcal {O}}\left(n\cdot l\right)}$	ja	${\displaystyle {\mathcal {O}}\left(n\right)}$
MSD Radixsort	${\displaystyle {\mathcal {O}}\left(n\cdot l\right)}$	nein	${\displaystyle {\mathcal {O}}\left(1\right)}$, in-place
Flashsort	${\displaystyle {\mathcal {O}}\left(n\right)\,..\,{\mathcal {O}}\left(n^{2}\right)}$	nein	${\displaystyle {\mathcal {O}}\left(1\right)}$

Dabei stellt ${\displaystyle n}$ die Anzahl der Elemente dar, ${\displaystyle k}$ die Anzahl der möglichen Werte und ${\displaystyle l}$ die Anzahl der Stellen des längsten Schlüssels.

Sortierung nach Beziehungen

Wenn n​icht mehr n​ach Eigenschaften, sondern n​ur noch n​ach paarweisen Beziehungen sortiert werden kann, s​o spricht m​an von e​iner topologischen Sortierung. Dies i​st beispielsweise d​er Fall, w​enn Aufgaben erledigt werden müssen, manche Aufgaben a​ber unbedingt vor anderen durchzuführen sind, b​ei anderen jedoch d​ie Reihenfolge k​eine Rolle spielt.

Für d​as topologische Sortieren g​ibt es Algorithmen, d​eren Laufzeit v​on der Anzahl d​er Beziehungen abhängt. Topologisches Sortieren i​st nicht möglich, w​enn gegenseitige (zyklische) Abhängigkeiten bestehen. Eine topologische Sortierung m​uss nicht eindeutig sein.

Wenn d​ie Beziehungen vollständig sind, a​lso für j​e zwei Objekte e​ine Abhängigkeit vorgegeben ist, s​o geht d​ie topologische Sortierung i​n eine gewöhnliche Sortierung über.

Indirektes Sortieren

In den Fällen, bei denen das Umstellen der Daten mit hohem Aufwand verbunden ist, kann man auch indirektes Sortieren anwenden. Man benötigt dazu zusätzlichen Speicher proportional zur Anzahl der Elemente (bspw. einen Zeiger auf das jeweilige Element, oder dessen Indexnummer im Basis-Array). Dann wird dieses Array sortiert und stellt somit einen (gemäß dem Vergleichskriterium) sortierten Index dar. Sollen die eigentlichen Daten anschließend ebenfalls in die richtige Reihenfolge gebracht werden, ist ein zusätzlicher Aufwand von ${\displaystyle \Theta \left(n\right)}$ erforderlich.

Ist a​uch der (wahlfreie) Zugriff a​uf die Elemente „teuer“, s​o werden mitunter a​uch diejenigen Datenkomponenten i​n den Index übernommen, d​ie in d​en Sortierschlüssel einfließen/der Sortierschlüssel sind. Dies benötigt d​ann weiteren zusätzlichen Speicherplatz.

Siehe auch: Adaptiertes 2-Phasen-2-Band-Mischen

Beweis der unteren Schranke für vergleichsbasiertes Sortieren

Es lässt sich beweisen, dass ein vergleichsbasiertes Sortierverfahren nicht schneller als ${\displaystyle \Omega (n\cdot \log(n))}$ sein kann:

Sei ${\displaystyle B}$ der Entscheidungsbaum für die Zahlenfolge ${\displaystyle X=(x_{1},\ldots ,x_{n})}$. Da alle Permutationen von ${\displaystyle X}$ das Ergebnis des Sortieralgorithmus sein könnten, muss der Entscheidungsbaum ${\displaystyle B}$ mindestens ${\displaystyle n!}$ Blätter haben. Da eine Mindestanzahl von Schritten gesucht ist, treten im Entscheidungsbaum keine unnötigen Vergleiche auf.

In einem Entscheidungsbaum mit ${\displaystyle n!}$ Blättern beträgt die maximale und die mittlere Tiefe eines Blattes mindestens ${\displaystyle \log(n!)}$. Da eine untere Schranke gesucht ist, kann ${\displaystyle n!}$ mittels ${\displaystyle n!\geq \left({\frac {n}{2}}\right)^{n/2}}$ nach unten hin abgeschätzt werden. Damit gilt ${\displaystyle \log(n!)\geq \left({\frac {n}{2}}\right)\cdot \log \left({\frac {n}{2}}\right)=\Omega (n\cdot \log(n))}$.

Es bleibt noch zu zeigen, dass in einem Binärbaum mit ${\displaystyle k}$ Blättern die maximale und die mittlere Tiefe eines Blattes mindestens ${\displaystyle \log(k)}$ beträgt. Angenommen ${\displaystyle B}$ sei ein Binärbaum, für welchen die obige Aussage nicht gilt. Seien ${\displaystyle T_{1}}$ und ${\displaystyle T_{2}}$ Teilbäume eines Binärbaumes mit ${\displaystyle k>2}$ Blättern. Für die Anzahl der Blätter ${\displaystyle k_{1}}$ in ${\displaystyle T_{1}}$ bzw. ${\displaystyle k_{2}}$ in ${\displaystyle T_{2}}$ gilt nun offensichtlich ${\displaystyle k_{1}<k}$, ${\displaystyle k_{2}<k}$ und ${\displaystyle k_{1}+k_{2}=k}$. Für die Tiefe jedes Blattes, bezogen auf die Wurzel von ${\displaystyle B}$, gilt:

${\displaystyle {\begin{aligned}{\text{mittlere Tiefe}}(B)&={\frac {k_{1}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{1})+1)+{\frac {k_{2}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{2})+1)\\&\geq {\frac {k_{1}}{k}}\cdot (\log(k_{1})+1)+{\frac {k_{2}}{k}}\cdot (\log(k_{2})+1)\\&={\frac {1}{k}}\cdot (k_{1}\cdot \log(2\cdot k_{1})+k_{2}\cdot \log(2\cdot k_{2}))\end{aligned}}}$

Das Minimum dieser Funktion liegt nun bei ${\displaystyle k_{1}+k_{2}=k}$ und ${\displaystyle k_{1}=k_{2}={\frac {k}{2}}}$. Eingesetzt in obige Formel ergibt das:

${\displaystyle {\text{mittlere Tiefe}}(B)\geq {\frac {1}{k}}\cdot \left({\frac {k}{2}}\cdot \log(k)+{\frac {k}{2}}\cdot \log(k)\right)=\log(k)}$.

Dies ergibt e​inen Widerspruch z​ur Annahme, w​omit obige Aussage bewiesen ist.

Literatur

• Donald E. Knuth: Sorting and Searching. In: The Art of Computer Programming. 2. Auflage. Band 3. Addison-Wesley, Boston 2003, ISBN 0-201-89685-0.
• Niklaus Wirth: Algorithmen und Datenstrukturen. 5. Auflage. Teubner Verlag, Stuttgart/Leipzig 1999, ISBN 3-519-22250-7.
• Robert Sedgewick: Algorithms in Java, Part 1–4. 3. Auflage. Addison-Wesley, Boston 2002, ISBN 0-201-36120-5.
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 3. Auflage. Oldenbourg Verlag, München 2010, ISBN 978-3-486-59002-9 (amerikanisches Englisch: Introduction to Algorithms. Übersetzt von Paul Molitor).
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 3. Auflage. The MIT Press, Cambridge MA / London 2009, ISBN 978-0-262-03384-8.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. 3. Auflage. Spektrum Verlag, Heidelberg/Berlin/Oxford 1996, ISBN 3-8274-0110-0.
• Anany Levitin: Introduction to The Design and Analysis of Algorithms. 2. Auflage. Pearson Addison-Wesley, Boston 2007, ISBN 978-0-321-36413-5.

Weblinks

• Quelltexte und Simulationen der Funktionsweise von Sortierverfahren (Bluffton University)
• Grafischer Vergleich Einige Sortieralgorithmen (Java)
• Video: visuelle und auditive Darstellung diverser Sortieralgorithmen (Timo Bingmann) auf YouTube