Quicksort

Einführung

Die Zerlegung in zwei Teile erfolgt anhand eines sogenannten Pivot-Elementes. Ein Element der Liste wird als Pivot Element ausgewählt und dann werden alle weiteren Elemente der zu sortierenden Liste mit diesem Element verglichen. Die zu sortierende Liste wird in zwei Bereiche unterteilt. Alle Elemente die kleiner sind als das Pivot-Element werden links von dem Pivot-Element einsortiert. Alle Elemente die größer sind, werden rechts von Pivot-Element abgelegt.

Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich dem Pivot-Element und somit auch kleiner oder gleich den Elementen der rechten Liste. Die Elemente der linken und rechten Liste sind je Liste noch unsortiert.

Anschließend muss man noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort.

Die Teillisten sind immer Abschnitte auf der ursprünglichen Liste, so dass kein zusätzlicher Speicher benötigt wird.

Beispiel

Als Beispiel betrachten wir eine Liste mit Zahlen. Wir wählen immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 zufällig das Pivot-Element.

7 10 8 6 11 4 9 3 1 5 2 12

Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen größer 7 haben sind rot markiert. Als ersten Schritt ändert QuickSort die Liste folgendermaßen:

4 3 1 6 1 4 7 9 11 8 10 12

Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, stehen rechts. Die Reihenfolge der Zahlen in den Teillisten ist hier willkürlich und hängt ab von der jeweiligen Implementierung. Entscheidend ist, dass alle Zahlen die kleiner sind als 7 links stehen und alle Zahlen die größer sind als 7 rechts.

Als nächstes wird der Teil links von der 7 wieder per QuickSort sortiert. Als Pivot wird die Zahl 3 gewählt. Die Zahlen die kleiner sind als 3 werden wieder blau markiert. Alle Zahlen größer 3 sind rot. Die Zahl 7 und die größeren Zahlen betrachten wir im Moment nicht, deshalb sind sie gelb hinterlegt:

3 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:

1 2 3 6 5 4 7 9 11 8 10 12

Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:

1 2 3 4 5 6 7 9 11 8 10 12

Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und größeren Zahlen auf die jeweils richtige Seite gebracht.

Der grundsätzlichen Algorithmus lässt mit PseudoCode wie folgt beschreiben:

Pseudocode

(http://de.wikipedia.org/wiki/Quicksort)

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei rekursiv immer weiter geteilt, bis sie nur noch einen Wert enthält.

funktion quicksort(links, rechts)

falls links < rechts dann

teiler := teile(links, rechts)

quicksort(links, teiler-1)

quicksort(teiler+1, rechts)

ende

ende

Wahl des Pivot-Elements

Die Wahl des Pivotelements ist wichtig. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervalls endet. Mit linkem oder rechten Element ist nicht das Element gemeint, welches sich in der unsortierten Liste ganz Links (im Beispiel die 7) oder rechts befindet, sondern das kleinste (im Beispiel die 1) bzw. das größte Element (im Beispiel die 12). Der QuickSort ist dann am Effizientesten, wenn man ein Pivot-Element wählt, welches am Schluss genau in der Mitte zu liegen kommt (im Beispiel die 6 oder die 7). Leider ist dieses Element nicht ganz einfach zu finden.

Man sollte deshalb nicht immer wie im Beispiel das erste Element als Pivot wählen. Dies ist zwar leicht zu implementieren, allerdings führt dies zu einem langsamen "QuickSort", falls das Array bereits sortiert ist, oder nahezu sortiert ist.

Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.

Java Implementierung

Bisher wurde die allgemeine Funktionsweise des Quicksorts beschrieben. Am Besten lassen sich komplexe Algorithmen nachvollziehen, wenn Sie anhand einer Implementierung mit Hilfe eines Debuggers analysiert werden. Mit Hilfe des Quicksorts können beliebige Datenstrukturen sortiert werden. In der folgenden Java Implementierung wird ein Array bestehend aus Integern (kurz int) sortiert.

public void quickSort(int array[], int links, int rechts) {

if (links < rechts) {

int i = teile(array,links,rechts);

quickSort(array,links,i-1);

quickSort(array,i+1,rechts);

}

}

public int teile(int array[], int links, int rechts) {

int pivot, i, j, help;

pivot = array[rechts];

i = links;

j = rechts-1;

while(i<=j) {

if (array[i] > pivot) {

// tausche x[i] und x[j]

help = array[i];

array[i] = array[j];

array[j] = help;

j--;

} else i++;

}

// tausche x[i] und x[rechts]

help = array[i];

array[i] = array[rechts];

array[rechts] = help;

return i;

}

Laufzeitanalyse

cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)

Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort O(n^2).

Best Case