Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/QuickSort

QuickSort

In diesem Kapitel wird der Sortieralgorithmus QuickSort behandelt.

Idee

Es gibt eine rekursive Aufteilung (wie bei MergeSort), aber hier werden Mischvorgänge vermieden (speicherintensiv!). Die Teillisten werden in zwei Hälften geteilt bezüglich eines Pivot-Elements, wobei in einer Liste alle Elemente größer als das PivotElement sind und in der anderen Liste alle kleiner. Das Pivot Element ist ein beliebiges Element der Liste/Folge, z.B. das linke, mittlere oder rechte Element.

Beispiel

Vertauschen von Elementen

Für gegebenes Pivot-Element p wird die Folge von links durchsuchen, bis das Element gefunden wurde, das größer oder gleich p ist. Und gleichzeitig wird die Folge von rechts durchsuchen, bis das Element gefunden ist, das kleiner p ist. Dabei werden die Elemente ggf. getauscht.

Sortierprinzip

Sortieren einer Folge F[u...o] nach dem „divide-and-conquer“Prinzip. Divide heißt die Folge F[u...o] wird in zwei Teilfolgen F[u...p-1] und F[p+1...o] geteilt. Die zwei Teilfolgen haben folgende Eigenschaften:

F[i] ≤ F[p] für alle i = u,...,p-1
F[i] > F[p] für alle i = p+1, …, o

Conquer bedeutet, dass die Teilfolgen sortiert werden. Mit combine werden die Teilfolgen zu F[u...o] verbunden. Vergleiche sind an dieser Stelle nicht erforderlich, da die Teilfolgen bereits sortiert sind.

Pivot Element

Im Prinzip muss man nicht das letzte Element als Pivot‐Element wählen. Je nach Verteilung der Daten, kann es sinnvoll sein ein anderes Element zu wählen. Wenn beispielsweise die Liste schon fast sortiert ist, sollte man immer das mittlere Element wählen Eine optimale Rekursion erhält man, wenn man immer den Median als Pivot-Element wählt (dieser ist aber nicht direkt bestimmbar, dafür müsste man die Liste erst sortiert haben. Hat man ein Pivot-Element ausgewählt, tauscht man dies einfach mit dem letzten Element und benutzt den Algorithmus wie zuvor.

Algorithmus

void quickSort(int[] F, int u, int o) {
     if (u < o) {
        int p = (u+o)/2;
        int pn = zerlege(F,u,o,p);
        quickSort(F,u,pn-1);
        quickSort(F,pn+1,o);
     }
int zerlege(int[] F, int u, int o, int p) {
     int pivot = F[p];
     int i = u;
     int j = o;    
  
     while (i < j) {
         while (F[i] < pivot)
             i++;
         while (F[j] > pivot)
             j--;
         if (i < j) {
             swap(F,i , j );
         }
     }
     return i;
} 
int zerlege(int[] F, int u, int o, int p) {     
     int pivot = F[p];

     //Tausche Pivot-Element mit dem letzten Element 
     //kann entfallen, wenn immer p=o gewählt wird
     swap(F,p, o);    
     int pn = u;

     //bringe kleinere Elemente nach vorne und größere nach hinten
     for (int j = u; j < o; j++) {    
          if (F[j] <= pivot){ 
               swap(F,pn, j );
               pn++;
          }
     }

     //bringe das Pivot-Element an die richtige Position und gebe diese zurück
     swap(F,pn, o);     
     return pn;
} 

void swap(int[] f, int x, int y){   //Hilfsmethode zum Vertaucshen
   int tmp = f[x];
   f[x] = f[y];
   f[y] = tmp;
}

}

P gibt an ,an welcher Position das Pivot Element ist. Bei diesem Beispiel ist es in der Mitte. Es kann aber auch an Stelle o oder u sein.

Beispiel 1

Zerlege (F,0,6,3) mit 3=(0+6)/2

8	2	1	5	9	7	3

...

3	2	1	5	9	7	3

Beispiel 2

Sei f[8]=5 das Pivot-Element

8	9	2	6	7	3	4	1	5

Suche von links aus das Element, welches kleiner als das Pivot-Element ist

8	9	2	6	7	3	4	1	5

Vertausche mit dem ersten größeren Element

2	9	8	6	7	3	4	1	5

Suche das nächste kleinere Element als die 5

2	9	8	6	7	3	4	1	5

Vertausche dieses mit dem zweiten größeren Element

2	3	8	6	7	9	4	1	5

Suche wieder das nächste kleinere Element

2	3	8	6	7	9	4	1	5

und vertausche dies mit dem dritt größeren Element

2	3	4	6	7	9	8	1	5

2	3	4	6	7	9	8	1	5

2	3	4	1	7	9	8	6	5

nun ist man rechts angekommen und hier wird nun das Pivot-Element getauscht

2	3	4	1	5	9	8	6	7

Von nun an steht das Pivot-Element an seiner finalen Position. Alle Elemente links vom Pivot-Element sind kleiner und alle auf der rechten Seite sind größer. Das bedeutet, dass nun ein rekursiver Abstieg für die Folgen

2	3	4	1

und

9	8	6	7

beginnen würde. Wenn das letzte Element wieder als Pivot-Element gewählt werden würde, dann hat die erste erste Folge nun das Pivot-Element 1 und in der zweiten Folge währe es das Element 7.

Alternative: Zerlegung mit while-schleifen

Man wählt zuerst ein Pivotelement, beispielsweise das mittlere Element. Nun beginnt man von unten an und vergleicht die Einträge mit dem Pivot. Danach beginnt man von oben und vergleicht die Elemente mit dem Pivot. Wenn ein Element kleiner bzw. größer ist als das Pivot Element, dann wird dieses Element getauscht.

Analyse

Theorem der Terminierung

Das Theorem der Terminierung besagt, dass der Algorithmus quickSort für jede Eingabe int[]F nach endlicher Zeit terminiert.

Beweis

In jedem rekursiven Aufruf von quickSort ist die Eingabelänge um mindestens 1 kleiner als vorher und die Rekursionsanfang ist erreicht wenn die Länge gleich 1 ist. In der Methode split gibt es nur eine for‐Schleife, dessen Zähler j in jedem Durchgang inkrementiert wird. Da u<o wird die for‐Schleife also nur endlich oft durchlaufen.

Theorem der Korrektheit

Das Theorem der Korrektheit besagt, dass der Algorithmus quickSort das Problem des vergleichsbasierten Sortierend löst.

Beweis

Die Korrektheit der Methode swap ist zunächst offensichtlich. Zeige nun, dass nach Aufruf pn=split(f,u,o,p) für u<o und $p\in [u,o]$ gilt:

f[p] wurde zu f[pn] verschoben

Dies ist klar (vorletzte Zeile der Methode split)

f[i] ≤ f[pn] für i=u,...,pn‐1

pn wird zu anfangs mit u initialisiert und immer dann inkrementiert, wenn die Position f[pn] durch ein Element, das kleiner/gleich dem Pivot‐Element ist, belegt wird.

f[i] > f[pn] für i=pn+1,...,o

Folgt aus der Beobachtung, dass in 2.) immer „genau dann“gilt. Beachte zudem, dass Element immer getauscht werden, also die Elemente im Array stets dieselben bleiben.

Die Korrektheit der Methode quickSort folgt nach Induktion nach der Länge von f (n=f.length):

  n=1: Der Algorithmus terminiert sofort und ein einelementiges Array ist stets sortiert
  n→n+1: Nach Korrektheit von split steht das Pivot‐Element an der richtigen Stelle und links und rechts stehen jeweils nur kleinere/größere Element. Die beiden rekursiven Aufrufe von quickSort erhalten jeweils ein Array, das echt kleiner als n+1 ist (mindestens das Pivot‐Element ist nicht mehr Teil des übergebenen Arrays). Nach Induktionsannahme folgt die Korrektheit von quickSort.

Theorem der Laufzeit

Das Theorem der Laufzeit besagt, dass wenn als Pivot Element stets der Median des aktuell betrachteten Arrays gewählt wird, so hat der Algorithmus quickSort eine Laufzeit von $\Theta (n~log~n)$ .

Beweis

Es gilt zunächst, dass split $\in \Theta (n)(mit~n=o-u)$ . Ausschlaggebend ist hier die for-Schleife, die genau n-mal durchlaufen wird. Gilt nach dem Aufruf von split stets pn=(u+o)/2 (dies ist gleichbedeutend damit, dass das Pivot‐Element stets der Median ist), so erhalten wir folgende Rekursionsgleichung für quickSort:

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}n\leq 1\\2T((n-1)/2)+\Theta (n)&sonst\end{array}}\right.$

Die ist fast dieselbe Rekursionsgleichung wie für MergeSort und es folgt $T(n)\in \Theta (n~log~n).$

Doch was ist, wenn die Voraussetzung des Theorems nicht erfüllt ist und wir ungleiche Rekursionsaufrufe haben?

Theorem der Laufzeit 2

Das Theorem der Laufzeit besagt, dass der Algorithmus quickSort im schlechtesten Fall eine Laufzeit von $\Theta (n^{2})$ hat.

Beweis

Angenommen, die Aufteilung erzeugt ein Teilarray mit Länge n‐1 und ein Teilarray mit Länge 0 (Pivot‐Element ist also immer Minimum oder Maximum), dann erhalten wir folgende Rekursionsgleichung für die Laufzeit:

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}n\leq 1\\2T(n-1)+\Theta (n)&sonst\end{array}}\right.$

Durch Induktionsbeweis kann leicht gezeigt werden, dass $T(n)\in \Theta (n^{2})$ . Dies ist auch tatsächlich der schlechteste Fall.

Für den mittleren Fall kann gezeigt werden, dass quickSort einen Aufwand von $\Theta (n~log~n)$ hat (wie im besten Fall), die in $\Theta$ versteckten Konstanten sind nur etwas größer.

Bemerkung

Im Gegensatz zu MergeSort ist QuickSort durch die Vorgehensweise bei Vertauschungen instabil, d.h. relative Reihenfolge gleicher Schlüssel werden nicht notwendigerweise beibehalten.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.6 zu finden.