Sortierverfahren

Ein Sortierverfahren ist ein Algorithmus, der dazu dient, ein Tupel (i. A. ein Array) zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von 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 ${\mathcal {O}}(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 (bester Fall), Average Case (Durchschnittsverhalten) 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 zudem zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren.

Zudem unterscheidet man zwischen Sortierverfahren, die in-place (auch in situ) arbeiten, d. h. der zusätzliche Speicherbedarf ist unabhängig von der Anzahl der zu sortierenden Elemente (also konstant und meist gering), und solchen, bei denen er abhängig ist (out-of-place oder ex situ).

Und man unterscheidet auch zwischen natürlichen Sortierverfahren, die bei vorsortierten Daten schneller arbeiten als bei unsortierten Daten, und solchen, die es nicht tun. Algorithmen, bei denen der Kontrollfluss von den Daten abhängt, nennt man adaptiv und dementsprechend Sortierverfahren, die nicht von den Eingabedaten abhängen, nicht-adaptiv. Nicht-adaptive Algorithmen sind demnach besonders interessant für Hardware-Implementierungen.

Manuelles Sortieren (etwa von Karteikarten) sowie elektro-mechanische Sortierverfahren (z. B. für Lochkarten) entsprechen meist einem der hier beschriebenen softwarebasierten Sortierverfahren, oder Mischtypen.

Vergleichsbasiertes Sortieren

Allgemeine Verfahren basieren auf dem paarweisen Vergleich der zu sortierenden Elemente. Bei der Komplexitätsanalyse wird davon ausgegangen, dass der Aufwand zum Vergleich zweier Elemente konstant ist.

Sortierverfahren	Best-Case	Average-Case	Worst-Case	Stabil	Zusätzlicher Speicherbedarf (sofern nicht in-place)
Binary Tree Sort (höhen-balanciert)	${\mathcal {O}}(n)$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	ja	${\mathcal {O}}(n)$
Binary Tree Sort	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n^{2})$	ja	${\mathcal {O}}(n)$
Bubblesort	${\mathcal {O}}(n)$	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	ja	–
Combsort	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n^{2})$	nein	–
Gnomesort	${\mathcal {O}}(n)$	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	ja	–
Heapsort	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	nein	–
Insertionsort	${\mathcal {O}}(n)$	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	ja	–
Introsort	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	nein	${\mathcal {O}}(\log(n))$
Merge Insertion	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	ja	implementierungsabhängig keine, ${\mathcal {O}}(n)$ oder ${\mathcal {O}}(n\cdot \log(n))$
Mergesort	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	ja	bei Arrays: ${\mathcal {O}}(n)$, je nach Implementierung auch ${\mathcal {O}}(n\cdot \log(n))$
Natural Mergesort	${\mathcal {O}}(n)$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	ja	bei Arrays: ${\mathcal {O}}(n)$, je nach Implementierung auch ${\mathcal {O}}(n\cdot \log(n))$
Quicksort	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n^{2})$	nein	${\mathcal {O}}(\log(n))$ (je nach Implentierung nur im average case)
Selectionsort	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	nein	–
Shakersort (Cocktailsort)	${\mathcal {O}}(n)$	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	ja	–
Shellsort		${\mathcal {O}}(n\cdot \log(n)^{2})$	${\mathcal {O}}(n^{1,25})$	nein	–
Smoothsort	${\mathcal {O}}(n)$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	nein	${\mathcal {O}}(n\cdot \log(n))$ für den Stack
Stoogesort	${\mathcal {O}}(n^{2,71})$	${\mathcal {O}}(n^{2,71})$	${\mathcal {O}}(n^{2,71})$	nein	–
Swap-Sort	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	${\mathcal {O}}(n^{2})$	–	–
Timsort	${\mathcal {O}}(n)$	${\mathcal {O}}(n\cdot \log(n))$	${\mathcal {O}}(n\cdot \log(n))$	ja	implementierungsabhängig ${\mathcal {O}}(n)$ oder ${\mathcal {O}}(\log(n))$

Unsinnige Sortierverfahren

Sortierverfahren	Best-Case	Average-Case	Worst-Case	Stabil	Zusätzlicher Speicherbedarf (sofern nicht in-place)
Bogosort	${\mathcal {O}}(n)$	${\mathcal {O}}(n\cdot n!)$	$\infty$	nein	–
Slowsort	${\mathcal {O}}\left(n^{\frac {\log(n)}{(2+e)}}\right)$	${\mathcal {O}}\left(n^{\frac {\log(n)}{2}}\right)$		nein	–

Nicht-vergleichsbasiertes Sortieren

Bei Sortierverfahren, die nicht auf Vergleichen beruhen, kann ein linearer Anstieg der benötigten Zeit mit der Anzahl der zu sortierenden Elemente erreicht werden. 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 Zahlenwerten gleicher Ordnung abgebildet werden kann).

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

Dabei stellt n die Anzahl der Elemente dar, k die Anzahl der möglichen Werte, m die Differenz aus Maximal- und Minimalwert der Eingabe und d die Anzahl der Stellen der längsten Eingabe.

Sortierung nach Beziehungen

Wenn nicht mehr nach Eigenschaften, sondern nur noch nach paarweisen Beziehungen sortiert werden kann, so spricht man von einer topologischen Sortierung. Dies ist beispielsweise der Fall, wenn Aufgaben erledigt werden müssen, manche Aufgaben aber unbedingt vor anderen durchzuführen sind, bei anderen jedoch die Reihenfolge keine Rolle spielt.

Für das topologische Sortieren gibt es Algorithmen, deren Laufzeit von der Anzahl der Beziehungen ${\mathcal {O}}\left(m\right)$ abhängt. Topologisches Sortieren ist nicht möglich, wenn gegenseitige (zyklische) Abhängigkeiten bestehen. Eine topologische Sortierung muss nicht eindeutig sein.

Wenn die Beziehungen vollständig sind, also für je zwei Objekte eine Abhängigkeit vorgegeben ist, so geht die topologische Sortierung in eine gewöhnliche Sortierung über. Das Laufzeitverhalten der Algorithmen bei n Objekten ist dann ${\mathcal {O}}\left(1\right)$.

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 indirekt 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 ${\mathcal {O}}\left(n\right)$ erforderlich.

Ist auch der (wahlfreie) Zugriff auf die Elemente „teuer“, so werden mitunter auch diejenigen Datenkomponenten in den Index übernommen, die in den Sortierschlüssel einfließen. Dies benötigt dann 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 $\Omega (n\cdot \log(n))$ sein kann:

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

In einem Entscheidungsbaum mit $n!$ Blättern beträgt die maximale und die mittlere Tiefe eines Blattes mindestens $\log(n!)$. Da eine untere Schranke gesucht ist, kann $n!$ mittels $n!\geq \left({\frac {n}{2}}\right)^{n/2}$ nach unten hin abgeschätzt werden. Damit gilt $\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 $k$ Blättern die maximale und die mittlere Tiefe eines Blattes mindestens $\log(k)$ beträgt. Angenommen $B$ sei ein Binärbaum, für welchen die obige Aussage nicht gilt. Seien $T_{1}$ und $T_{2}$ Teilbäume eines Binärbaumes mit $k>2$ Blättern. Für die Anzahl der Blätter $k_{1}$ in $T_{1}$ bzw. $k_{2}$ in $T_{2}$ gilt nun offensichtlich $k_{1}<k$, $k_{2}<k$ und $k_{1}+k_{2}=k$. Für die Tiefe jedes Blattes, bezogen auf die Wurzel von $B$, gilt:

${\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 $k_{1}+k_{2}=k$ und $k_{1}=k_{2}={\frac {k}{2}}$. Eingesetzt in obige Formel ergibt das:

${\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 einen Widerspruch zur Annahme, womit 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

Commons: Sortieralgorithmen – Sammlung von Bildern, Videos und Audiodateien

• Quelltexte und Simulationen der Funktionsweise von Sortierverfahren (Bluffton University)
• Grafischer Vergleich Einige Sortieralgorithmen (Java)