Quicksort

Definition

Das Sortierverfahren gehört zu den rekursiven und nicht stabilen Sortieralgorithmen. Er lässt sich aus dem englischen quick = schnell und sort = sortieren ableiten und wurde in den sechziger Jahren von C. Antony R. Hoare in seiner Grundform entwickelt. Der Quicksort Algorithmus arbeitet wie der Mergesort nach dem Teile-und-herrsche-Verfahren (englisch „divide and conquer“) der Informatik.

direkt ins Video springen

Pivotelement

Hier noch eine kurze Definition zum Pivotelement. Das Pivotelement leitet sich vom französischem pivot = Dreh-/ Angelpunkt ab. Vielleicht kennst du es auch vom gaußsche Eliminationsverfahren  oder dem Basistauschverfahren. Genau wie in der Informatik, also beim Quicksort, handelt es sich dabei immer um ein Element einer Zahlenmenge, welches als Erstes von einem Algorithmus bestimmt wird, um eine bestimmte Berechnung durchzuführen. Innerhalb des Sortierverfahrens stellt das Element sozusagen eine Aufteilungsgrenze dar. Dabei wird dann jeweils nach dem kleinsten oder betragsmäßig größten Element in der aktuellen (Teil-)Liste gesucht und rekursiv sortiert. Die Auswahl des Elements wird Pivotisierung genannt.

Quicksort Erklärung

Das genaue Prinzip hinter dem Quicksort kann man nicht unbedingt verallgemeinern. Es kann gewisse Abweichungen durch die jeweils verwendete Programmiersprache geben, wodurch der Ablauf tatsächlich unterschiedlich beeinflusst werden kann. Trotzdem gibt es ein gewisses Grundprinzip. Hier findest du eine Quicksort Erklärung für eine allgemeine Funktionsweise.

Pivotelement bestimmten

Dafür kann man eigentlich alle Elemente verwenden. Heißt also für uns, dass wir sowohl das erste als auch das letzte Element, einen Wert aus der Mitte oder sogar einen Zufallswert auswählen können. Für eine optimale Rekursion verwendet man aber eigentlich immer den Median . Am besten du orientierst dich aber dabei an deinem Uni-Skript, damit du weißt, was dein Dozent bevorzugt. Nehmen wir exemplarisch mal das erste Element als unser Pivotelement.

Teile und herrsche

Das Pivot-Element wird dann in die Mitte gesetzt und die restlichen Werte sortiert. Einmal nach links, wenn sie kleiner sind und einmal nach rechts, wenn sie größer sind. Dabei muss man die Elemente immer der ursprünglichen Reihenfolge nach von links nach rechts in ihrem Bereich einordnen.

Rekursiver Quicksort-Aufruf

Rekursiver Quicksort-Aufruf für beide Teile des Arrays (Vor und nach dem Pivot-Element):

Das Pivot-Element ist danach an seinem richtigen Platz und es müssen Neue bestimmt werden. Natürlich wieder das erste Element, aber diesmal in beiden Bereichen. Der Vorgang wird wiederholt, somit werden die restlichen Elemente wieder genau im selben Schema neben den Pivot-Elementen eingeordnet. Im nächsten Schritt haben alle neuen Pivot-Elemente keine Vergleichswerte mehr und sind damit auch direkt richtig platziert. Damit sind alle Werte sortiert.

Quicksort Beispiel – Allgemein

Beim Quicksort solltest du besonders darauf achten, in welcher Form es von deiner Uni verlangt ist! Der Grund ist ganz einfach der, dass der Quicksort sehr von der Programmiersprache abhängig ist und dabei dann tatsächlich auch unterschiedlich ablaufen kann. Heißt für dich also, dass du dich unbedingt an die gewünschte Version deines Professors halten solltest. Wir zeigen dir jetzt erst einmal ein sehr allgemeines Quicksort Beispiel, mit dem du den Sortieralgorithmus sehr gut verstehen solltest. Zusätzlich zeigen wir dir auch noch ein Beispiel, welches eine typische In-Place Variante darstellt. Schau dir doch für deine benötigte Variante einfach unser Video an.

Fangen wir doch direkt mit dem allgemeinen Beispiel an. Gegeben sei dabei die folgende Liste:

[6] [8] [2] [5] [9] [1] [7] [3] [4]

Pivot-Element bestimmen

Zuerst müssen wir dafür unser Pivot-Element bestimmen. Dafür gibt es aber keine standardisierte Richtlinie. Heißt für uns, wir können die erste Zahl, die letzte Zahl oder auch eine zufällige Zahl auswählen. Am besten du orientierst dich an der Aufgabenstellung oder nimmst die Variante, die dein Dozent in den Vorlesungen verwendet. Wir nehmen in unserem Fall als Pivot-Element einfach mal die erste Zahl – also die 6.  Die Zahl 6 markieren wir rot und schreiben sie uns in die Mitte.

Sortieren

Jetzt müssen die restlichen Zahlen entsprechend einsortiert werden. Die Zahlen die kleiner als 6 sind kommen dabei nach links. Die Größeren kommen dann logischerweise nach rechts. Starten wir also mit der 8. Sie ist größer als die 6 und wird an die erste Stelle rechts neben dem Pivot-Element hingeschrieben. Dann kommt die 2. Sie ist kleiner als die 6 und wird automatisch auf die erste Position im linken Bereich eingeordnet. Genau das gleiche machen wir dann auch mit der 5. Die kommt nur eine Stelle weiter neben die 2. Die 9 ist größer als die 6 und wird nach rechts neben die 8 geschrieben. Danach kommt die 1, die wir automatisch nach links sortieren. Die 7 packen wieder nach rechts und die 3 und die 4 wieder nach links.

[2] [5] [1] [3] [4] [6] [8] [9] [7]

Zweiter Durchlauf

Jetzt müssen wir wieder neue Pivot-Elemente bestimmen. Wir wählen wieder die erste Zahl, aber diesmal aus beiden Bereichen. Einmal aus dem linken Bereich die 2 und einmal aus dem rechten Bereich die 8. Dann startet das Ganze wieder von vorne, aber wir sortieren dabei nur einmal die linke Seite bis zur 6. Und einmal die rechte Seite ab der 6.

[1] [2] [5] [3] [4] [6] [7] [8] [9]

Dritter Durchlauf

Anschließend müssen wir wieder neue Pivot-Elemente bestimmen. Natürlich wieder die ersten Zahlen. Das sind einmal die 1 und die 7 auf der linken Seite. Und einmal die 5 und die 9 auf der rechten Seite. Die 1 hat keine Vergleichswerte mehr, also ist sie auf der richtigen Position. Somit müssen wir erst wieder die 3 und die 4 richtig einsortieren, nämlich links neben der 5. Bei der 7 und der 9 ist es derselbe Fall, wie bei der 1. Sie sind einzelne Elemente und sind damit auch schon richtig platziert.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

Nun bleiben nur noch die 3 und die 4 übrig. Die 3 ist wieder unsere erste Zahl also unser Pivot-Element und die 4 wird entsprechend rechts eingeordnet.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

Die 4 wird jetzt unser neues Pivot-Element und damit ist das Array fertig sortiert. Wir können jetzt alle unsere rot markierten Zahlen nach unten in eine Reihe schreiben und haben unsere sortierte Liste.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

[1] [2] [3] [4] [5] [6] [7] [8] [9]

Quicksort Beispiel – In-Place

Für die tatsächliche In-Place-Variante nehmen wir dieselbe Liste, wie gerade eben für das allgemeine Quicksort Beispiel:

[6] [8] [2] [5] [9] [1] [7] [3] [4]

Pivot-Element bestimmen

Als erstes müssen wir ein Pivot-Element bestimmen. Dafür gibt es wie auch schon vorhin keine allgemeine Regel.

Diesmal gibt es aber noch zusätzlich ein i, welches immer ganz links in der restlichen Zahlenreihe steht. Und dazu gibt es dann auch noch ein j, welches ganz rechts in der Zahlenreihe steht. Das i durchläuft die Zahlenreihe nach rechts und sucht nach Zahlen, die größer als das Pivot-Element sind. Das j sucht im Gegensatz dazu kleinere Werte und läuft dabei auch nach links.

direkt ins Video springen

In unserem Fall ist es direkt passend. Die 8 ist größer und die 4 kleiner als die 6. Und in dieser Variante tauschen dann diese Zahlen direkt ihren Platz. Das i sucht weiter nach einer größeren Zahl und findet dann die 9 und das j die kleinere Zahl 3. Wir tauschen die beiden. Dann findet das j als Nächstes die 1 und das i als Nächstes 7. Dabei überkreuzen sich die beiden aber, weshalb zu diesem Zeitpunkt der Durchlauf dann immer für den aktuellen Vorgang beendet ist. Dann wird nur noch das j mit dem Pivot-Element getauscht, wenn das j kleiner ist. Die 1 ist kleiner, also kann getauscht werden.

 [1] [4] [2] [5] [3] [6] [7] [9] [8]

Wichtig! Wenn unser Pivot-Element am Anfang ganz rechts gewesen wäre, hätten wir es mit unserem i vergleichen müssen! Du hättest also geprüft, ob das i-Element größer als dein Pivot-Element ist. Genauso, wie du in unserem Fall prüfst, ob j kleiner ist. Das kommt daher, weil wir ja durch i und j die restliche Liste schon in größer und kleiner als das Pivot-Element aufgeteilt haben. Unser Pivot-Element muss also folglich in die Mitte.

Zweiter Durchlauf

Aber zurück zur Aufgabe! Damit haben wir also unsere aktuelle Liste [1] [4] [2] [5] [3] [6] [7] [9] [8]. Das Pivot-Element 6 ist damit dann schon auf seiner richtigen Position. Wir können also wieder 2 neue Pivot-Elemente bestimmen. Einmal im linken Bereich bis zur 6 und einmal im rechten Bereich nach der 6. Natürlich nehmen wir dafür wieder in beiden Fällen die erste Zahl, also die 1 und die 7. Wir sortieren auch wieder das i als erstes Element aus der restlichen Liste und j als letztes Element. Dabei aber wieder auf beiden Seiten!

Starten wir also gleich mal mit dem linken Bereich. Die 4 ist direkt wieder größer, aber keine Zahl ist kleiner als die 1. Damit überkreuzen sich i und j direkt wieder beim Durchlaufen. Damit ist der Durchgang ohne Tausch beendet. Die 1 ist also direkt auf der richtigen Position, da wir ja schon wissen, dass es kein kleineres Element gibt. Auf der rechten Seite sind wieder beide Zahlen größer und damit ist wie vorhin auch schon der Durchlauf beendet. Die 7 ist somit auch offiziell auf dem richtigen Platz.

[1] [4] [2] [5] [3] [6] [7] [9] [8]

Letzte Schritte

Dann beginnen wir wieder von vorn. Diesmal mit der 4 und der 9 als Pivot-Element. Wir wiederholen den Vorgang und tauschen zum Schluss wieder die 4 mit dem aktuellen j, welches nach dem Überkreuzen mit i die 3 ist. Die 9 wird mit der 8 getauscht und beide sind damit auch fertig sortiert.

[1] [3] [2] [4] [5] [6] [7] [8] [9]

Unsere neuen p’s sind nun die 3 und die 5. Die 5 steht da allein und ist somit auch richtig positioniert. Also haben wir nur noch die 3 und die 2 zum Sortieren. Damit ist unser letztes Pivot-Element die 2.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

[1] [2] [3] [4] [5] [6] [7] [8] [9]

[1] [2] [3] [4] [5] [6] [7] [8] [9]

Jetzt sind wir dann auch endlich fertig! Zum Schluss haben wir wieder unsere sortierte Liste.

Quicksort Pseudocode

Da die meisten von euch auf das typische In-Place-Verfahren als Vorlage stoßen, schauen wir uns doch einfach mal den Algorithmus dahinter an. Das meint hauptsächlich, dass kein zusätzlicher Speicher benötigt wird, da wir direkt innerhalb der Liste tauschen können. Dadurch können die Teillisten in sich sortiert werden, womit dann auch direkt zum Schluss die Gesamtliste geordnet ist.

funktion quicksort (li, re)
  if li 
    t = teilen(li, re)
    quicksort(li, t)
    quicksort(t+1, re)
  end
end
 
funktion teilen(li, re)
  i = li – 1
  j = re + 1
  pivot = Liste[(li + re) / 2]
  while Liste[i] 
    i++
  while Liste [j] > pivot
    j++
  if (i 
    int a = Liste[i]
    Liste[i] = Liste[j]
    Liste[j] = a
  else return j

Quicksort Struktogramm

Im Folgenden siehst du ein Quicksort Struktogramm  bzw. das Nassi-Schneidermann-Diagramm des Algorithmus. Die Bezeichner sind an den obigen Pseudocode angepasst.

direkt ins Video springen

Quicksort Java

Hier zeigen wir jetzt noch, wie sich die Implementierung als Quicksort Java-Code darstellen lässt. Der Code ist dabei in zwei Hälften geteilt – die Arbeitsweise des Sortierens und die Methode Teilen.

Java – Sortieren

public static int[] Liste;
public int[] quicksort(int li, int re) {
  int t;
  if (li 
    t = teilen(li, re);
    quicksort(li, t);
    quicksort(t + 1, re);
  }
  return Liste;

Java – Teilen

int teilen(int li, int re) {
  int i, j, pivot = Liste[(li + re) / 2];
  i = li – 1;
  j = re + 1;
  while (true) {
    do {
      i++;
    } while (Liste[i] 
    do {
      j–;
    } while (Liste[j] > pivot);
    if (i 
      int a = Liste[i];
      Liste[i] = Liste[j];
      Liste[j] = a;
    } else {
      return j;
    }
  }
}

Quicksort C++

Im Folgenden siehst du eine mögliche Implementierung eines Quicksort C++ Codes:

void quicksort(int liste[], int li, int re) {
  int i = li, j = re;
  int a;
  int pivot = liste[(li + re) / 2];
  while (i 
    while (liste[i] 
      i++;
    while (liste[j] > pivot)
      j–;
    if (i 
      a = liste[i];
      liste[i] = liste[j];
      liste[j] = a;
      i++;
      j–;
    }
  };
  if (li 
    quicksort(liste, li, j);
  if (i 
    quicksort(liste, i, re);
}

Quicksort Laufzeit

Wie der Name Quicksort schon andeutet, handelt es sich hierbei um einen sehr schnellen Sortieralgorithmus. Die Quicksort-Laufzeit beträgt im:

• Worst-Case:
• Average-Case:
• Best-Case:

Der Worst-Case wäre der Fall, wenn beispielsweise das Pivotelement immer das letzte Element ist und die Liste eigentlich schon sortiert ist. Im Allgemeinen ist das Eintreffen des Worst-Case also abhängig von dem Ansatz der Wahl des Pivotelements und kann entsprechend unterschiedlich groß sein. Dabei würden die Teillisten immer nur um eins kleiner werden. Das kommt aber in der Praxis ziemlich selten vor.

Im Best-Case ist die Laufzeit genau wie im Durchschnitt. Man geht dabei von dem Fall aus, dass man das Pivotelement so wählt, dass die Teillisten immer möglichst gleich groß sind. Die Länge der größeren Teilliste ist dabei im Schnitt  und die Tiefe damit .

Aufgrund seiner Komplexität gehört der Quicksort in der Praxis tatsächlich zu den beliebtesten Sortieralgorithmen. Er ist zum einen schnell und man kann davon ausgehen, dass der Worst-Case so gut wie nie auftritt. Zusätzlich ist die Implementierung, sollten wir eine Rekursion zur Verfügung haben, ziemlich einfach.

Speicherplatzkomplexität

Der Quicksort gilt allgemein als In-Place-Verfahren, da dabei die zu Sortierenden Elemente innerhalb der Liste vertauscht werden und kein zusätzlicher Speicherplatz benötigt wird. Der Speicherverbrauch ist vom Pivot-Element und der Art der vorhandenen Daten abhängig. Die Stapelgröße beträgt im:

• Worst-Case:
• Average-Case: