Folge 13:

Quicksort

13.1 Grundprinzip des Quicksort

Gegeben ist ein unsortierter Array von Elementen, z.B. ganzen Zahlen

Schritt 1

Gegeben ist ein unsortierter Array von ganzen Zahlen. Ein Element des Arrays wird nun besonders behandelt, es wird nämlich zum so genannten Median befördert.

Im Grunde ist es egal, welches der Arrayelemente zum Median wird, in unterschiedlichen Büchern findet man verschiedene Verfahren. Häufig wird zum Beispiel das letzte Element des Arrays genommen, in diesem Skript nehmen wir das mittlere Element des Arrays bzw. das Element links von der Mitte (bei geradzahliger Arraylänge).

Das Element 50 wäre hier ein geeigneter Median, das Element liegt ziemlich in der Mitte des Arrays, und sein Wert liegt ungefähr in der Mitte des Zahlenbereichs. Wie wir einen geeigneten Median finden, ist jetzt nicht unser Problem, hier geht es nur um das Grundprinzip des Quicksort.

Durch den gewählten Median wird der Array in zwei Partitionen zerlegt, in eine linke und in eine rechte:

Schritt 2

Alle Elemente der linken Partition, die größer sind als der Median, werden in die rechte Partition verfrachtet. Und alle Elemente der rechten Partition, die kleiner sind als der Median, werden in die linke Partition verfrachtet:

Die 60 ist z.B. nach rechts geschafft worden, die 18 und die 17 nach links. Dadurch ist der Median um eine Position nach rechts gewandert.

Der sortierte Teil des Arrays besteht jetzt aus der Zahl 50. Diese Zahl ist bereits an der richtigen Position: Alle Zahlen links der 50 sind kleiner, alle Zahlen rechts der 50 sind größer.

Schritt 3

Nun müssen die beiden Partitionen auf genau die gleiche Weise verändert werden, wie in den Schritten 1 und 2 besprochen. So entstehen aus der linken Partition zwei neue Partitionen (LL = links-links und LR = links-rechts) und aus der rechten Partition ebenfalls (RL und RR):

Das Grundprinzip des Quicksort müsste jetzt eigentlich klar sein: „Teile und herrsche". Das heißt hier: Teile den Array in zwei (im optimalen Fall gleich große) Hälften, ordne die Zahlen so an, dass alle Elemente links vom Median kleiner und alle rechts vom Median größer sind als der Median, und verfahre dann mit den beiden Hälften analog, solange, bis es nicht mehr weitergeht, weil der Array sortiert ist.

13.2 Der Quicksort im Detail

In der folgenden Abbildung sehen Sie den Quicksort-Algorithmus von Robert SEDGEWICK aus dem Buch „Algorithmen in C":

In einem unsortierten Array ist es völlig egal, welches Element als Median gewählt wird; die Wahrscheinlichkeit, dass ein Element das kleinste, das größte oder ein mittleres ist, ist bei allen Elementen eines unsortierten Arrays völlig gleich. Daher wählt der SEDGEWICK-Algorithmus einfach das rechte Element als Median.

1. Grundprinzip des Quicksort
2. Der Quicksort im Detail
3. Optimierungen

In der Buchversion des Lehrgangs wird der Quicksort im Detail auf drei Seiten an einem konkreten Beispiel Schritt für Schritt erläutert. Aus technischen Gründen sehe ich mich nicht in der Lage, die dazu erforderlichen aufwändigen Graphiken in dieser Webversion zu reproduzieren.

13.3 Optimierungen des Quicksort

Es sind schon viele Versuche unternommen worden, den Quicksort, der ja als schnellster Sortieralgorithmus gilt, noch weiter zu optimieren.

Ein erster und wirklich effektiver Ansatz ist es, das Pivot-Element etwas sorgfältiger auszuwählen. Im Idealfall hat das Pivot-Element einen mittleren Wert, so dass etwa gleich viele Elemente kleiner bzw. größer als das Pivot-Element sind. Das ergibt dann zwei ungefähr gleich große Partitionen.

Ein praktischer Ansatz ist es, einfach drei beliebige Array-Elemente zu wählen und dann das Element mit dem mittleren Wert als Pivot-Element zu nehmen (median-of-three).

In dem obigen Beispiel hat man das linke, das mittlere und das rechte Element genommen. Das Element mit dem Index 7 hat den „mittleren Wert„, die 16 ist nämlich kleiner und die 47 größer als dieses Element.

Etwas rechenintensiver wäre es, wenn man in einem ersten Schritt den Mittelwert des gesamten Arrays berechnen würde. In unserem Beispiel wäre der Mittelwert gerundet 39. Die 40 an Position 4 wäre daher ein geeignetes Pivot-Element. Testen wir doch einmal, welche Partitionen wir mit der 40 als Pivot-Element erhalten würden: 16, 12, 30, 20, 13, 35, 27, 16 und 33 wären kleiner als die 40, das sind 9 Elemente von 16. Die 70, 40, 50, 80, 56, 82 und 47 wären nicht kleiner als die 40, das sind 7 Elemente. Wir würden in der Tat zwei ungefähr gleich große Partitionen bekommen, die linke mit 9 Elementen, die rechte mit 6 Elementen. Das Pivot-Element gehört ja zu keiner Partition. Vergleicht man das mit dem Ergebnis des SEDGEWICK-Algorithmus, so ist der Unterschied aber nicht wesentlich, hier erhielten wir eine linke Partition mit 10, eine rechte mit 5 Elementen.

Ein zweiter Ansatz, den Quicksort zu optimieren, beruht auf der Überlegung, dass der Quicksort eigentlich nur für große Zahlenmengen sehr schnell ist. Bei kleinen Arrays oder bei kleinen Partitionen ist der Quicksort dagegen aufwändiger als beispielsweise der Insertionsort. Daher legt man einen Schwellenwert Min fest, der die minimale Partitionsgröße angibt, bei der nach dem Quick-sort vorgegangen werden soll. Wird im Laufe des Quicksort bei einem rekursiven Aufruf dieser Schwellenwert für eine Partition unterschritten, so wird diese Partition nach dem Insertionsort-Algorithmus sortiert. Einen Idealwert für Min scheint es nicht zu geben. Allerdings haben Experimente mit mehreren Millionen von Array-Elementen gezeigt, dass Min = 25 ein recht guter Schwellenwert ist.

und weiter mit Folge 14 - Abstrakte Datentypen

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 21. Juni 2005 und überarbeitet am 30. Mai 2009.