miaowang.de - Quick Sort

QuickSort ist ein sehr bekannter und schneller vergleichsbasiertes Sortierverfahren entwickelt von C. Antony R. Hoare. QuickSort ist in der Praxis bedeutend schneller als seine Konkurrenten mit selber Komplexität von O(n log n), weil die innere Schleife des Algorithmus auf den meisten Architekturen besonders effizient implementiert werden kann. Genauso wie MergeSort ist Quicksort ein gutes Beispiel für das Teile-und-Herrsche Prinzip. Das Verfahren wird als in-place angesehen, obwohl die Rekursion zusätzlichen Stackspeicher benötigt. Ein vergleichsweise schneller Algorithmus, der in-place arbeitet ist HeapSort. Nachteile an QuickSort ist, dass es instabil sortiert und vergleichweise schlecht abschneidet im Worst Case (O(n²⁾).

Ähnlich wie andere Teile-und-Herrsche Strategien besteht das Verfahren aus zwei Teilen: dem Aufteilen der zu sortierenden Folge in kleinere Teilfolgen und dem Zusammenfügen der Teilfolgen zu einer sortierten Gesamtfolge. Das Zerteilen in zwei Teilfolgen beginnt mit der Auswahl eines Elements aus der Folge, das Pivot-Element. Die restliche Folge wird in eine Teilfolge geteilt mit Elementen kleiner dem Pivot und einer Teilfolge mit Elementen größer dem Pivot. Gleichgroße Elemente können in eine beliebige Liste womit das Verfahren nicht stabil ist. Nach dem Aufteilen befindet sich das Pivot-Element an der korrekten Position in der sortierten Folge. Das Zusammenfügen ist lediglich die Konkatenation der Folge der kleineren Elemente zusammen mit dem Pivot und der Folge der größeren Elemente. Die Folge der kleineren Elemente und die Folge der größeren Elemente werden rekursiv erneut sortiert bis der Rekursionsanker (leere oder einelementrige Folge) erreicht ist.

Es gibt mehrere vielversprechende Strategien das Pivot-Element geschickt zu wählen, so dass der Algorithmus effizient abläuft. Im einfachsten Fall nimmt man das erste oder das letzte Element, was aber bei sortierten oder beinah sortierten Datenmengen schlecht abschneidet. Das mittlere Element zu wählen zeigt sich in der Praxis als besser, das Problem des Worst Case bleibt jedoch erhalten. Um den Worst Case gänzlich auszuschließen wählt man das Pivot zufällig oder als Median. Im ersten Fall beträgt die erwartete Laufzeit dann O(n log n), garantiert jedoch nicht komplett, dass es keinen Worst Case gibt. Mit dem Median wird ein Worst Case verhindert, aber die Errechnung des Median bringt Mehrkosten von O(n) mit sich. So verbessert sich der Worst Case auf ebenfalls O(n log n), aber die Wahl des Medians zeigt sich in der Praxis oft als ineffizient, sodass an der Stelle andere Sortierverfahren bevorzugt werden.

Das Teile-und-Herrsche Prinzip wird ebenfalls vom MergeSort verwendet, wobei dort das Aufteilen einfach ist, während das Zusammenfügen teuer. Bei QuickSort ist das Aufteilen aufwendig, das Zusammenfügen lediglich eine Konkatenation.

Das Applet (benötigt Java) visualisiert einen QuickSort auf maximal 16 Elemente. In jedem Schritt wird das erste Element als Pivot gewählt (schwarz). Die Folge wird dann in zwei Teilfolgen aufgeteilt mit Elementen kleiner als dem Pivot (rot) und Elementen größer als dem Pivot (grün). Der Vorgang wird rekursiv weitergeführt bis die Folge sortiert ist. Mit Insert lassen sich Werte zur Folge hinzufügen, mit Random Fill erhält man eine zufällige volle Folge generiert und mit Clear löscht man die aktuelle Folge. Mit einem Klick auf Sort wird stets ein Schritt des Verfahrens visualisiert.

Dies ist ein rekursiver QuickSort wobei das erste Element stets als Pivot-Element gewählt wird. Die zwei Teilfolgen werden aufgeteilt, indem zwei Zeiger von außen ins Zentrum wandern und dabei überprüfen, ob sie auf der richtigen Seite liegen. Stoppen beide Zeiger bei einem Element auf der falschen Seite werden diese vertauscht. Zum Schluss wird das Pivot-Element zwischen die Teilfolgen gebracht.

QuickSort verdankt seiner Schnelligkeit dadurch, dass weit voneinander entfernte Elemente vertauscht werden. Je kleiner die Folge wird, desto ineffizienter wird QuickSort und nähert sich seinem Worst Case. Um dieses Problem zu verhindern, wird bei kleineren Folgen oftmals auf ein anderes Sortierverfahren gewechselt, wie z.B. InsertionSort oder HeapSort. IntroSort ist solch ein Algorithmus, der mit QuickSort startet und zu HeapSort wechselt, sobald eine gewisse vorher definierte Rekursionstiefe erreicht wurde.

Im Best Case wird jedes Mal die Folge in zwei nahezu gleich große Teilfolgen aufgeteilt. Wird für einen Durchlauf einer Folge mit n Elementen T(n) Zeit benötigt, so wird zur Bestimmung des ersten Elements als Pivot konstante Zeit gebraucht, n Schritte für das Durchlaufen und Aufteilen der Liste und zwei rekursive Aufrufe von QuickSort auf Teilfolgen der halben Länge (2T(n/2)). Dies ergibt eine Rekursionsgleichung von T(n) = 2T(n/2) + n, welches sich mittels Master Theorem zu T(n) ∈ O(n log n) auflöst.

Im Worst Case jedoch (falls die Liste invers sortiert ist) werden Teilfolgen der Länge 1 und n-1 erzeugt. In diesem Fall entartet der Rekursionsbaum zu einer linearen Kette von n verschachtelten Aufrufen. Die Rekursionsgleichung beträgt nun T(n) = O(n) + T(1) + T(n-1), welches T(n) ∈ O(n²) ergibt. Alternativ überlegt man sich, dass jeder i-te Iterationsschritt O(n-i) durchlaufen muss, was folgende Rechnung ergibt:
$QuickSort worst case complexity$