Home > Informatik > Stufe Q1

13. Mergesort und Quicksort

Mergesort

Der Mergesort ist eigentlich ein recht einfaches Sortierverfahren, das deutlich schneller ist als die drei Sortierverfahren, die wir in der Stufe EF kennengelernt haben.

Aber wie wird das Array sortiert? Ganz einfach:

  • Der Array wird zunächst in zwei möglichst gleich große Hälften aufgeteilt. Jede Hälfte wird dann sortiert. Anschließend werden die beiden Hälften wiedervereinigt, so dass der ganze Array sortiert ist.

Aber wie wird jede dieser Hälften sortiert? Ganz einfach:

  • Jede Hälfte wird zunächst in zwei möglichst gleich große Viertel aufgeteilt. Jedes dieser beiden Viertel wird dann sortiert. Anschließend werden die beiden Viertel wiedervereinigt, so dass die ganze Hälfte sortiert ist.

Aber wie wird jedes dieser Viertel sortiert? Ganz einfach:

  • Jedes Viertel wird zunächst in zwei möglichst gleich große Achtel aufgeteilt. Jedes dieser beiden Achtel wird dann sortiert. Anschließend werden die beiden Achtel wiedervereinigt, so dass das ganze Viertel sortiert ist.

Aber wie wird jedes dieser Achtel sortiert? Ganz einfach:

  • wir machen genau so weiter wie obe beschrieben ...

Am besten kann man den Mergesort durch ein rekursives Verfahren realisieren. Dass es sich bei dem Algorithmus um eine Rekursion handelt, sollten Sie bereits an den Formulierungen erkannt haben, die ich zur Beschreibung des Verfahrens verwendet habe.

Weitere Einzelheiten zum Mergesort erfahren Sie auf der Seite "Mergesort".

Quicksort

Der Quicksort ist ein komplexeres Sortierverfahren — und zugleich eines der schnellsten, die es gibt. Die Grundidee: Man zerlegt ein großes Array in zwei kleinere und sortiert diese auf die gleiche Weise. Solche Verfahren, die sich dabei selbst aufrufen, nennt man rekursive Verfahren. Ein erstes Beispiel dafür haben wir bereits mit dem Mergesort kennengelernt.

Es gibt mehrere verschiedene Varianten des Quicksorts, wir betrachten hier eine besonders anschauliche. Wie immer bei der Besprechung von Sortier- und Suchalgorithmen gehen wir von einem Array mit int-Werten aus.

Der Algorithmus

Schritt 1: Ein Pivotelement wählen

Wir wählen eine Zahl aus dem Array aus — bei unserer Variante die Zahl in der Mitte — und bezeichnen sie als Pivotelement (oder kurz: Pivot). Das Pivotelement ist der Vergleichsmaßstab, an dem sich alles Weitere orientiert.

Schritt 2: Links und rechts sortieren

Nun durchlaufen wir das Array von der Mitte aus nach links und rechts:

  • In der linken Hälfte suchen wir die nächste Zahl, die größer ist als das Pivot.
  • In der rechten Hälfte suchen wir die nächste Zahl, die kleiner ist als das Pivot.
  • Diese beiden Zahlen tauschen wir: Die kleinere wandert nach links, die größere nach rechts.

Das machen wir so lange, bis wir das linke bzw. rechte Ende des Arrays erreicht haben.

Schritt 3: Das Ergebnis eines Durchgangs

Nach einem solchen Durchgang stehen alle Zahlen, die kleiner sind als das Pivot, links vom Pivot — und alle Zahlen, die größer sind, rechts davon. Allerdings sind die Zahlen innerhalb der beiden Array-Hälften noch unsortiert.

Schritt 4: Wiederholen

Jetzt wenden wir das gleiche Verfahren auf die linke Hälfte und getrennt davon auf die rechte Hälfte an — und danach wieder auf deren Hälften, und so weiter. Sind die Teile schließlich nur noch ein Element groß, ist das gesamte Array sortiert.

Visualisierung eines Beispiels

Die folgende Graphik wurde von der KI Mistral Vibe erstellt und als SVG-Graphik exportiert.

Der Quicksort in Einzelschritten Sortiert wird ein Array mit 16 unsortierten int-Zahlen zwischen 1 und 100: 19 79 64 25 7 100 12 56 41 94 48 85 91 72 97 33 Pivotelement (Vergleichsmaßstab) von der linken Suche gefunden (zu groß) von der rechten Suche gefunden (zu klein) steht endgültig richtig gehört nicht zum aktuellen Teilbereich Tausch der beiden gefundenen Zahlen 1. Durchgang · Pivot: 56 (Index 7) — die Suche läuft von der Mitte nach außen 19 79 64 25 7 100 12 56 41 94 48 85 91 72 97 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Startzustand: Die Zahl in der Array-Mitte (Index 7) wird zum Pivot. 19 79 64 25 7 100 12 56 41 94 48 85 91 72 97 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Linke Suche (←) findet 100 > 56, rechte Suche (→) findet 41 < 56 — tauschen! 19 79 64 25 7 41 12 56 100 94 48 85 91 72 97 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Nächster Fund: links 64 > 56, rechts 48 < 56 — tauschen! 19 79 48 25 7 41 12 56 100 94 64 85 91 72 97 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Dritter Fund: links 79 > 56, rechts 33 < 56 — tauschen! 19 33 48 25 7 41 12 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Ende des 1. Durchgangs: Alle Zahlen < 56 stehen links, alle > 56 rechts — die 56 hat ihren endgültigen Platz. 2. Durchgang · linke Hälfte (Index 0–6) · Pivot: 25 (Index 3) 19 33 48 25 7 41 12 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Das gleiche Verfahren wird nun auf die linke Hälfte angewendet: Pivot ist die 25 in der Mitte (Index 3). 19 33 48 25 7 41 12 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Links: 48 > 25 · Rechts: 7 < 25 — tauschen! 19 33 7 25 48 41 12 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Links: 33 > 25 · Rechts: 12 < 25 — tauschen! 19 12 7 25 48 41 33 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Ergebnis: Die 25 steht endgültig — links davon nur Zahlen < 25, rechts nur Zahlen > 25. 2. Durchgang · rechte Hälfte (Index 8–15) · Pivot: 85 (Index 11) 19 12 7 25 48 41 33 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Parallel zur linken Hälfte: In der rechten Hälfte ist die 85 (Index 11) das Pivot. 19 12 7 25 48 41 33 56 100 94 64 85 91 72 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Links: 94 > 85 · Rechts: 72 < 85 — tauschen! 19 12 7 25 48 41 33 56 100 72 64 85 91 94 97 79 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Links: 100 > 85 · Rechts: 79 < 85 — tauschen! 19 12 7 25 48 41 33 56 79 72 64 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Ergebnis: Auch die 85 steht endgültig. 3. Durchgang · die vier kleinen Teilbereiche 19 12 7 25 48 41 33 56 79 72 64 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Teilbereich Index 0–2, Pivot 12: Links 19 > 12 · Rechts 7 < 12 — tauschen! 7 12 19 25 48 41 33 56 79 72 64 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Der Bereich 0–2 ist vollständig sortiert. 7 12 19 25 48 41 33 56 79 72 64 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Teilbereich Index 4–6, Pivot 41: Links 48 > 41 · Rechts 33 < 41 — tauschen! 7 12 19 25 33 41 48 56 79 72 64 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Der Bereich 4–6 ist vollständig sortiert. 7 12 19 25 33 41 48 56 79 72 64 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Teilbereich Index 8–10, Pivot 72: Links 79 > 72 · Rechts 64 < 72 — tauschen! 7 12 19 25 33 41 48 56 64 72 79 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Der Bereich 8–10 ist vollständig sortiert. 7 12 19 25 33 41 48 56 64 72 79 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Teilbereich Index 12–15, Pivot 94: Hier gibt es nichts zu tauschen — die 91 steht bereits auf der richtigen Seite. Damit ist auch dieser Bereich fertig. Endergebnis 7 12 19 25 33 41 48 56 64 72 79 85 91 94 97 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Alle Teilbereiche sind sortiert — das gesamte Array ist fertig. Insgesamt genügten 10 Tauschoperationen.

Bei diesem Beispiel handelt es sich um einen sehr einfachen Fall, bei dem jede größere Zahl der linken Seite stets einen Tauschpartner auf der rechten Seite findet. Es kann natürlich auch passieren, dass sich in der linken Partion vier zu große Zahlen befinden, in der rechten Partition aber nur zwei oder drei zu kleine Zahlen.

Für solche Fälle gibt es aber eine (im Prinzip) gute Vermeidungsstrategie: Wählt man als Pivot den echten Median des Bereichs, kann der Fall gar nicht erst entstehen, dann gibt es nämlich zwangsläufig genau so viele zu große Zahlen links wie zu kleine Zahlen rechts. Allerdings muss der Median erst in einem Array-Durchlauf ermittelt werden.

Median

Unter dem Median eines Datensatzes versteht man den Wert, der in der sortierten Reihenfolge genau in der Mitte liegt. Es gibt daher genauso viele Werte, die kleiner sind als der Median, wie Werte, die größer sind.

Bei einer geraden Zahl von Werten nimmt man häufig den Durchschnitt der beiden mittleren Werte (statistische Konvention) oder wählt einen der beiden mittleren Werte.

Allerdings ist die Bestimmung des Medians selbst ein aufwändiger Prozess, daher verwendet man in der Praxis meistens andere Verfahren für die Bestimmung des Pivot-Elements.