Lektion 2.2

Schnelles Sortieren: Mergesort, Quicksort und die untere Schranke

35 min Lesezeit

Die einfachen Verfahren brauchen für eine Million Zahlen rund $10^{12}$ Schritte. Das ist unnötig viel. Ein wichtiges Prinzip der Algorithmik kann hier helfen: Teile und herrsche (englisch Divide and Conquer). Man zerlegt ein großes Problem in kleinere Probleme derselben Art, löst diese rekursiv und setzt die Teilergebnisse zusammen.

Warum das beim Sortieren hilft: Zwei sortierte Hälften lassen sich in einem einzigen Durchlauf zu einer sortierten Folge zusammenführen. Und zwei kleine Aufgaben der Größe $\frac n2$ sind zusammen viel billiger als eine Aufgabe der Größe $n$ , wenn der Aufwand quadratisch wächst: $2 \cdot (\frac n2)^2 = \frac{n^2}{2}$ .

Definition

Mergesort (Sortieren durch Mischen)

Mergesort arbeitet in drei Schritten:

1. Teilen: Zerlege die Folge in zwei gleich große Hälften.
2. Herrschen: Sortiere beide Hälften rekursiv mit Mergesort. Eine Folge der Länge $1$ ist bereits sortiert.
3. Mischen: Führe die beiden sortierten Hälften zusammen. Dazu vergleichst du immer die vordersten Elemente beider Hälften und übernimmst das kleinere.

Der Mischschritt braucht für insgesamt $n$ Elemente höchstens $n-1$ Vergleiche, also $O(n)$ . Die Rekursion halbiert die Länge in jedem Schritt und hat deshalb $\log_2 n$ Ebenen. In jeder Ebene wird insgesamt $O(n)$ gemischt. Daraus ergibt sich der Gesamtaufwand, auch im schlechtesten Fall. Der Preis ist zusätzlicher Speicher der Größe $n$ für das Mischen.

T(n) = 2\,T\!\left(\tfrac n2\right) + O(n) \;\Longrightarrow\; T(n) \in O(n \log n)

Beispiel

Mergesort auf $[3, 1, 4, 2]$

Teilen: $[3, 1, 4, 2] \to [3, 1]$ und $[4, 2] \to [3], [1]$ und $[4], [2]$ .

Mischen, untere Ebene: $[3]$ und $[1]$ ergeben $[1, 3]$ . $[4]$ und $[2]$ ergeben $[2, 4]$ .

Mischen, obere Ebene: Vergleiche die vorderen Elemente von $[1, 3]$ und $[2, 4]$ : $1 < 2$ , nimm $1$ . Dann $3$ gegen $2$ : nimm $2$ . Dann $3$ gegen $4$ : nimm $3$ . Übrig bleibt $4$ .

[1, 3] \;\text{und}\; [2, 4] \;\longrightarrow\; [1, 2, 3, 4]

Die Rekursionstiefe beträgt $\log_2 4 = 2$ . Bei $n = 16$ wären es $4$ Ebenen, bei $n = 10^6$ nur etwa $20$ .

Definition

Quicksort

Quicksort teilt anders: Wähle ein Element als Pivot. Ordne die übrigen Elemente so um, dass links vom Pivot nur kleinere und rechts nur größere Elemente stehen (Partitionieren). Danach steht der Pivot an seiner endgültigen Position, und die beiden Seiten werden rekursiv sortiert. Ein Mischschritt entfällt, und es wird kaum Zusatzspeicher benötigt.

Die Laufzeit hängt davon ab, wie ausgeglichen die Seiten sind. Teilt der Pivot die Folge etwa in der Mitte, ergibt sich wie bei Mergesort $O(n \log n)$ . Ist der Pivot immer das kleinste oder größte Element (zum Beispiel immer das erste Element bei bereits sortierter Eingabe), schrumpft das Problem nur um $1$ pro Schritt, und es entsteht $n + (n-1) + \dots + 1 \in O(n^2)$ . Mit einem zufällig gewählten Pivot tritt dieser Fall mit sehr geringer Wahrscheinlichkeit auf, und die erwartete Laufzeit ist $O(n \log n)$ .

\text{im Mittel } O(n \log n), \qquad \text{im schlechtesten Fall } O(n^2)

Satz

Untere Schranke für vergleichsbasiertes Sortieren

Jedes Sortierverfahren, das nur durch Vergleiche zweier Elemente entscheidet, braucht im schlechtesten Fall mindestens $\lceil \log_2(n!) \rceil$ Vergleiche. Das ist von der Größenordnung $n \log n$ . Mergesort ist also bis auf konstante Faktoren optimal.

\log_2(n!) \in \Theta(n \log n)

Zusammenfassung

Teile und herrsche: Problem teilen, Teilprobleme rekursiv lösen, Ergebnisse zusammensetzen.
Mergesort halbiert, sortiert rekursiv und mischt: stets $O(n \log n)$ , stabil, braucht $O(n)$ Zusatzspeicher.
Quicksort partitioniert um ein Pivot: im Mittel $O(n \log n)$ , im schlechtesten Fall $O(n^2)$ .
Vergleichsbasierte Verfahren brauchen mindestens $\log_2(n!) \in \Theta(n \log n)$ Vergleiche.
Mergesort ist daher asymptotisch optimal unter den vergleichsbasierten Verfahren.

Übungen

Aufgabe 1Numerisch

Wie viele Ebenen hat die Rekursion von Mergesort für eine Folge der Länge $16$ , bis die Teilfolgen die Länge $1$ haben? (Zähle die Teilungsschritte.)

Aufgabe 2Numerisch

Mindestens wie viele Vergleiche braucht ein vergleichsbasiertes Sortierverfahren im schlechtesten Fall, um fünf verschiedene Elemente zu sortieren?

Aufgabe 3Multiple Choice

Wann liefert Quicksort mit dem ersten Element als Pivot den ungünstigsten Fall $O(n^2)$ ?

Aufgabe 4Freitext

Mische die sortierten Folgen $[2, 5, 8]$ und $[1, 6, 7, 9]$ zu einer sortierten Folge und gib an, wie viele Vergleiche dabei ausgeführt werden.

Mergesort auf [3,1,4,2][3, 1, 4, 2][3,1,4,2]

Zusammenfassung

Übungen

Mergesort auf $[3, 1, 4, 2]$