Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 15. Mai 2005 um 14:54 Uhr durch WhileTrue(Diskussion | Beiträge). Sie kann sich erheblich von der aktuellen Version unterscheiden.
funktion teile(daten, 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
4↑
9
3
3
8
2
7
6
7
1
5
Da der Algorithmus neu begonnen hat, steht der rote Index und der Zeiger auf dem ersten Element. Ein Vergleich zeigt, dass die Vier kleiner als das Pivotelement ist.
4↑
9
3
3
8
2
7
6
7
1
5
Der rote Index wandert zum zweiten Element, da alle Elemente links von dem Index kleiner als das Pivotelement sind.
4
9↑
3
3
8
2
7
6
7
1
5
Der Zeiger wandert zum zweiten Element und vergleicht dieses mit dem Pivotelement.
4
9
3↑
3
8
2
7
6
7
1
5
Der Zeiger wandert zum dritten Element und erkennt, dass die Drei kleiner als das Pivotelement ist.
4
3
9↑
3
8
2
7
6
7
1
5
Das dritte Element (3) wird mit dem Indexelement vertauscht, der Index wandert zum dritten Element.
4
3
9
3↑
8
2
7
6
7
1
5
Der Zeiger wandert zum vierten Element (3) und erkennt, dass die Drei kleiner als das Pivotelement ist.
4
3
3
9↑
8
2
7
6
7
1
5
Elemententausch und Indexwanderung
4
3
3
9
8↑
2
7
6
7
1
5
Der Zeiger wandert zum nächsten Element (8). Da die Acht nicht kleiner ist als das Pivotelement passiert weiter nichts.
4
3
3
9
8
2↑
7
6
7
1
5
Der Zeiger wandert weiter und erkennt ein kleineres Element.
4
3
3
2
8
9↑
7
6
7
1
5
Tausch und Indexwanderung
4
3
3
2
8
9
7↑
6
7
1
5
Der Zeiger wandert.
4
3
3
2
8
9
7
6↑
7
1
5
Der Zeiger wandert.
4
3
3
2
8
9
7
6
7↑
1
5
Der Zeiger wandert.
4
3
3
2
8
9
7
6
7
1↑
5
Der Zeiger wandert und erkennt ein kleineres Element (1).
4
3
3
2
1
9
7
6
7
8↑
5
Tausch der Eins mit der Acht und der Index wandert weiter.
4
3
3
2
1
5
7
6
7
8↑
9
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 einen linken mit kleineren Elementen und in eine rechte mit größeren Elementen besetzte Liste teilt.
