Benutzer:WhileTrue/QuickSort
Zur Navigation springen
Zur Suche springen
Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus. Dabei ist daten das zu sortierende Feld.
funktion quicksort(links, rechts)
falls rechts > links
teiler := teile(links, rechts)
quicksort(links, teiler-1)
quicksort(teiler+1, right)
Die Funktion teile muss dabei das Feld so teilen, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen, zum Beispiel durch
funktion teile(links, rechts)
index := links
von zeiger := links bis rechts-1
falls daten[zeiger] <= daten[rechts]
tausche(index, zeiger)
index := index + 1
tausche(index, rechts)
antworte index
Mehr zur Funktion tausche findet sich im Artikel Dreieckstausch.
funktion tausche(a, b) temp := daten[a] daten[a] := daten[b] daten[b] := temp
| 4 | 9 | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Der Algorithmus startet mit einer Liste von 9 Elementen. Das rechte Element (5) wird als Pivotelement ausgewählt. Im folgenden werden alle größeren Elemente mit der Web-Farbe Honeydew und alle kleineren Elemente mit der Web-Farbe LemonChiffon hinterlegt. Das Indexelement wird rot hinterlegt und der Zeiger wird mit einem ↑ dargestellt. |
| 4↑ | 9 | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Am Anfang steht der rote Index und der Zeiger auf dem ersten Element. Im weiteren Algorithmus sind immer alle Elemente links vom Index kleiner gleich dem Pivotelement. Das Element unter dem Zeiger (4) wird mit dem Pivotelement (5) verglichen. |
| 4↑ | 9 | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Da aus dem Vergleich im vorigen Schritt hervorgeht, dass die 4 kleiner gleich dem Pivotelement (5) ist, wandert der rote Index zum zweiten Element.¹ |
| 4 | 9↑ | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Der Zeiger wandert zum zweiten Element (9) und vergleicht dieses mit dem Pivotelement (5). |
| 4 | 9 | 3↑ | 3 | 8 | 2 | 7 | 6 | 5 | Der Zeiger wandert zum dritten Element (3) und vergleicht dieses mit dem Pivotelement (5). |
| 4 | 3 | 9↑ | 3 | 8 | 2 | 7 | 6 | 5 | Da das dritte Element kleiner gleich ist, wird dieses mit dem Indexelement vertauscht und der Index wandert zum dritten Element. |
| 4 | 3 | 9 | 3↑ | 8 | 2 | 7 | 6 | 5 | Der Zeiger wandert zum vierten Element (3), dieses ist kleiner gleich dem Pivotelement. |
| 4 | 3 | 3 | 9↑ | 8 | 2 | 7 | 6 | 5 | Elemententausch und Indexwanderung. |
| 4 | 3 | 3 | 9 | 8↑ | 2 | 7 | 6 | 5 | Der Zeiger wandert zum nächsten Element (8). |
| 4 | 3 | 3 | 9 | 8 | 2↑ | 7 | 6 | 5 | Der Zeiger wandert weiter (2). Dieses Element ist kleiner gleich dem Pivotelement. |
| 4 | 3 | 3 | 2 | 8 | 9↑ | 7 | 6 | 5 | Tausch und Indexwanderung. |
| 4 | 3 | 3 | 2 | 8 | 9 | 7↑ | 6 | 5 | Der Zeiger wandert. |
| 4 | 3 | 3 | 2 | 8 | 9 | 7 | 6↑ | 5 | Der Zeiger wandert. |
| 4 | 3 | 3 | 2 | 5 | 9 | 7 | 6↑ | 8 | Da der Zeiger am Ende angekommen ist, wird das Pivotelement mit dem Indexelement getauscht. Der Index zeigt nun auf diejenige Position, welche die Liste in eine linken mit kleineren Elementen und in eine rechte mit größeren Elementen besetzte Liste teilt. |
¹ Eigentlich wird das erste Element mit sich selbst vertauscht, da Zeiger und Index auf dem gleichen Element liegen. Dies hat aber keine sichtbare Auswirkung.