Erklärung:

Quicksort ist eins der schnellsten Sortierverfahren. Dies liegt daran, dass Quicksort die zu sortierenden Elemente in Teilstücke zerlegt.
Eine Menge von Elementen wird in der Mitte zerteilt. Links sind alle Elemente die kleiner als das Element in der Mitte sind, rechts die
größeren Elemente. Diese beiden Teile werden nun wieder in der Mitte zerteilt. Der Aufruf dazu erfolgt rekursiv, dass heißt das die Funktion
sich immer wieder selbst aufruft bis ein bestimmter Zustand diese Schleife unterbricht. In diesem Fall wäre es ein komplett zerteiltes und
sortiertes Array. Nach dem zerteilen wird dieses Array wieder zu einem Stück zusammen gefügt.
Dieses Prinzip nennt sich Divide-and-Conquer und arbeitet in 3 Schritten:

1> Divide:          Das zu sortierende Array wird zerteilt
2> Conquer:       Die entstandenen Teile werden sortiert
3> Combine:      Die Teile werden wieder zusammen gefügt

Beispiel:


Schritt 1: Als erstes wird das mittlere Element gesucht. In unserem Fall ist das die 3


Schritt 2: Nun wird das Element an der Stelle i mit dem Element in der Mitte (x) verglichen. Dieses ist kleiner, also springt i eine Stelle weiter


Schritt 3: Jetzt wird die 5 mit der 3 verglichen. Diese ist >= 3 und wird daher in unserer Variable i gespeichert. Das selbe macht nun unsere Variable j. Sie läuft so lange nach links bis sie entweder ein kleineres Element als x gefunden hat, oder bis j gleich x ist.


Schritt 4: Das j hat nun eine Zahl gefunden welche kleiner als 3 ist. i und j werden nun getauscht.


Schritt 5: Das i sucht nun wieder nach einer Zahl die entweder größer oder gleich 3 ist. Da die beiden ersten Elemente schon "sortiert" wurden springt das i ein Feld weiter. Das Selbe passiert mit unserem j. Dieses sucht nach einem kleineren oder gleichem Wert wie x. Da die beiden rechten Elemente schon "sortiert" sind springt auch diese Variable auf das Feld x.


Schritt 6: Nun werden i und j wieder getauscht. Dies hat aber logischerweise keine Auswirkungen mehr auf unser Array. Danach wird das Array in 2 Teile zerteilt.




Diese beiden Teile werden nun wieder mit dem gleichen Verfahren behandelt bis das komplette Array sortiert
ist. Danach werden die Teile wieder zusammen gefügt.

Dieser Algorithmus ist leider nicht ganz so einfach zu verstehen, aber prinzipiell sind es nur folgende Schritte:

1>    Mittleres Element wählen
2a>  Suche von links aus das erste Element, das größer oder gleich x ist
2b>  Suche von rechts aus das erste Element, das kleiner oder gleich x ist
2c>  Vertausche die Werte in i und j, falls i<=j (i kleiner gleich j) und setze i und j eine Position weiter nach
        links bzw. rechts
3>    Wiederhole die Schritte 2a-c so lange bis i>j

Aufwand:

Quicksort benötigt bei einem durchschnittlichen Datensatz etwa O(n*log n) Vergleiche und O(n*log n) Vertauschungen.

>> Allgemeine Fragen oder Probleme mit dem Tutorial? Hier gehts zum Forum!