Stell dir vor, du hast eine riesige Liste und möchtest sie möglichst schnell sortieren. Wie machst du das? Also eine Möglichkeit ist das sortieren mit dem Quicksort Algorithmus. Die sort() Methode in Java ist ebenfalls ein Quicksort, aber was passiert denn nun eigentlich bei dem Verfahren?
Quicksort – was ist das? Eine Definition
Wie der Name schon andeutet handelt es sich bei Quicksort um einen schnellen Algorithmus zum sortieren von Daten (engl. „quick“=“schnell“, „(to) sort“ = „sortieren“)
Quicksort ist ein rekursiv aufgebauter Algorithmus der durch anwenden des „divide and conquer“ Prinzips auch größere Datenmengen mit wenig notwendigen Vergleichen sortieren kann.
Das „divide and conquer“ Prinzip
Das Verfahren arbeitet nach dem „divide and conquer“ (teile und herrsche) Prinzip. Du übergibst ihm also eine Liste (kann auch ein Array oder eine andere Datenstruktur sein) und innerhalb des Verfahrens wird diese Liste wieder und wieder zerlegt und so Stück für Stück sortiert.
Das „Teile und Herrsche“ Prinzip ermöglicht uns eine nicht vorsortierte Liste sehr schnell zu sortieren. Im Fall von Quicksort heiß sehr schnell, dass der Algorithmus im Durchschnitt \(\) O(n*log(n)) \(\) Schritte benötigt, um eine Liste zu sortieren. Das ist wirklich schnell. Im Vergleich: Wenn du die Liste mit Bubblesort sortieren würdest wären es \(\) O(n^2) \(\) Vergleiche im Durchschnitt, das entspricht dem worst case bei Quicksort.
sortieren mit Quicksort – das Verfahren
Wir wissen inzwischen das Quicksort zum sortieren seine Liste teilt, wie es das genau macht, gucken wir uns jetzt an. Die Idee hinter Quicksort ist, dass wir zu Beginn ein sogenanntes Pivotelement bestimmen. Das Pivotelement ist irgendein Element aus deiner Liste. Du kannst dabei der Einfachheit halber einfach das erste oder letzte Element der Liste nehmen. Es dient uns ausschließlich als Orientierung. Alle anderen Elemente werden links oder rechts neben ihm eingeordnet. Da uns aber ein einziges Teilen der Liste auch nicht unbedingt weiter bringt, wenden wir dasselbe Verfahren nun noch einmal auf jede der anderen beiden Seiten an. Das günstigste ist, wenn man das Anwenden des Verfahrens über einen rekursiven Aufruf der Methode quickSort regelt. Im Anschluss haben wir eine sortierte Liste.
Zeit für ein Beispiel
Unser Beispiel ist ein Array mit 9 Werten und sieht wie folgt aus:
- Pivotelement bestimmen
Zu aller erst bestimmen wir das Pivotelement. In diesem Schritt betrachten wir noch die vollständige Liste, also von Index 0 bis 8. Ich habe mich hier dazu entschieden das mittlere Element zu nehmen(du kannst aber auch das erste oder letzte verwenden). In meinem Fall ist es die 9.
- Suchen der ersten Elemente
Jetzt müssen wir auf der linken Seite nach dem ersten Element suchen, das größer ist als 9. Um das zu finden, gehen wir alle Elemente bis dahin durch, da alle kleiner sind endet unser linker Zeiger bei der 9. Der rechte Zeiger sucht inzwischen nach dem ersten Element, das kleiner ist als 9. Dadurch dass die 9 das größte Element in der Liste ist, ist die erste Zahl auch kleiner als die 9.
- Tauschen der Elemente
Im Anschluss tauschen wir unsere beiden gefundenen Zahlen.
Dadurch haben wir nun ein neues Pivotelement für den nächsten Durchlauf, die 4. - Nächster Durchlauf, vergleichen der Elemente
Jetzt fangen wir wieder von vorne an. Die 6 ist größer als 4, damit bleibt der erste Zeiger dort und die 3 ist die erste kleinere Zahl. Damit sind unsere nächsten Zahlen zum Tauschen gefunden.
Sobald sich beide Zeiger in der Mitte treffen und nichts finden können, wird die Liste geteilt und der Algorithmus auf die Teillisten angewendet. Das Pivotelement gilt dann als sortiert.
In der Darstellung sind alle sortierten Elemente dick umrandet. - weitere Durchläufe bis die Liste sortiert ist
Das ganze wiederholen wir solange, bis die Liste sortiert ist.
Im Bild seht ihr dann wie der weitere Ablauf für unser Beispiel aussieht.
Sortieren mit Quicksort in Java
Also unser Algorithmus besteht insgesamt aus 2 Methoden:
- der Methode „
quickSort(int left, int right, double[] unsorted)
“ die uns am Ende die fertig sortierte Liste zurückgibt und - der Methode „
divide(int left, int right, double[] unsorted)
„, sie teilt unsere Liste.
Die Quicksort Implementierung, die ich dir hier zeige, arbeitet rekursiv. Das zeigt sich direkt zu Beginn in der Methode quickSort
. Also was passiert dort? Gucken wir uns das mal genauer an.
Die Methode bekommt insgesamt 3 Parameter übergeben. Da das Verfahren in-place arbeitet benötigen wir ein Intervall das wir betrachten. Unser benötigtes Intervall bekommen wir mit den ersten zwei Parametern. Sie geben an von wo bis wo die Liste sortiert werden soll. Als dritter Parameter übergeben wir noch die Liste die sortiert werden soll.
Methode quickSort(int, int, double[])
- Danach bestimmen wir unser Pivot Element. Dafür verwende ich hier den Mittelwert der Liste, du kannst aber auch einfach den ersten oder letzten Wert nehmen.
Wir bestimmen den Mittelwert wie folgt:
public static double[] quickSort(int left, int right, double[] unsorted){ int pivot; //Enthält die Liste mehr als 1 Element? if(left < right){ //Dann teile (und sortiere) die Liste pivot = divide(left, right, unsorted);
Da wir das selbe Verfahren auf jeder Seite anwenden müssen, kommt jetzt der rekursive Aufruf:
//Sortieren der linken Seite (Anfang bis mitte) quickSort(left, pivot, unsorted); //Sortieren der rechten Seite (Mitte+1 bis Ende) //Wir müssen das Pivot-Element um eins erhöhen, sonst wäre es doppelt enthalten quickSort(pivot+1, right, unsorted); } return unsorted;
Sobald die Liste nur noch ein Element hat fängt sie an diese Werte zurück zu geben und ist damit am Ende angekommen.
Bisher haben wir nicht einen einzigen Wert getauscht, also gucken wir uns mal die Methode divide
genauer an.
divide(int, int, double[])
Genau wie die quicksort Methode enthält die divide Methode auch drei Parameter, die linke und rechte Grenze und die Liste selber.
Zu Beginn bestimmt die Methode das pivotElement. Dazu teilt sie die Größe der Liste durch 2 und bestimmt das Element aus dem Array.
Anschließend deklarieren wir 2 temporäre Variablen mit der linken und rechten Grenze. Dadurch das wir gleich die Elemente tauschen und dafür die Grenzen wandern lassen, ist dieser Schritt notwendig.
public int divide(int left, int right, double[] unsorted){
int pivot = (int) unsorted[(left+right) / 2];
int i = left;
int j = right;
Wir lassen jetzt die beiden Grenzen gegeneinander laufen und suchen die Elemente die größer/kleiner sind als das Pivotelement. Wir suchen links nach dem ersten Element, das größer ist als das Pivotelement und rechts nach dem ersten, das kleiner ist. Das heißt, die Suche ist beendet, sobald i gleich groß mit j ist.
while (i < j){ //Grenzen laufen gegeneinander //Wir bekommen das erste größere Element wenn wir unsere linke Grenze so oft erhöhen bis wir eins gefunden haben while(unsorted[i] < pivot){i++;} //Das selbe machen wir mit der rechten Seite //nur suchen wir hier das erste kleinere Element while(unsorted[j] > pivot){j--;} //Wenn wir in der ersten Hälfte eins gefunden haben(i=links < rechts=j)können wir die Elemente tauschen, sonst stehen sie richtig if(i < j){ double temp = unsorted[i]; System.out.println(unsorted[i] + " <-> " +unsorted[j]); unsorted[i] = unsorted[j]; unsorted[j] = temp; } else return j;
Zuerst suchen wir nach dem ersten Element, das größer ist als das Pivotelement, aber links steht. Dazu erhöhen wir unser i solange wie das nicht zutrifft.
Dasselbe machen wir jetzt mit j. Hier verringern wir den Wert so lange wie kein Element kleiner ist als das Pivotelement.
Wenn dann i kleiner ist als j werden die beiden Werte miteinander getauscht. Andernfalls gibst du j zurück.
Zum Merken findest du hier noch ein kurzes Merkblatt zu Quicksort:
Es gibt natürlich noch viele andere Sortieralgorithmen neben Quicksort. Du kannst dir hier mal einen kleinen Überblick zum Thema verschaffen. Ausführliche Beiträge zu den anderen Sprachen werden folgen.
Lass doch einfach einen Like oder Kommentar da, und erzähl mir wie dir der Beitrag gefallen hat.