Ausgangspunkt ist wieder das unsortierte Zahlenarray:
|
58 |
4 |
43 |
7 |
29 |
64 |
13 |
Beim "Quicksort", entwickelt von Sir Charles Antony Richard Hoare wird das Feld ebenfalls wie beim Straight Selection Sort in zwei Teile zerlegt. Dabei wird allerdings nicht nur ein Element vom einen Teil in den anderen gebracht, sondern es wird das Feld in ungefähr zwei gleich große Teile zerlegt. Im ersten Teil sollen die kleineren Elemente liegen, im zweiten Teil jeweils die größeren, allerdings am Anfang jeweils noch unsortiert. Dann wird jeder der beiden Teile für sich sortiert. Dabei wird natürlich erneut das Verfahren verwendet. Es wird also eine rekursive Lösung verwendet.
Wir müssen also zunächst dazu das Feld in zwei Teile zerlegen, von denen der zweite nur größere Elemente als der erste enthält. Danach ist der Quicksort auf die beiden Teile anzuwenden.
Als Abbruchbedingung für die Rekursion ist der Fall anzusetzen, dass der Teilabschnitt nur noch ein Element enthält.
Die Zerlegung dabei mit folgenden Schritten
bis kl links von gr gefunden wird.
Beispiel:
|
58 |
4 |
43 |
7 |
29 |
64 |
13 |
|
-> |
<- |
Pivot ist das 4. Element p = 7
Suche von links (-> ) liefert gr=58, da 58 größer gleich p.
Suche von rechts (<-) liefert kl=7, da 7 kleiner gleich p.
Also wird getauscht: 58 <-> 7.
|
7 |
4 |
43 |
58 |
29 |
64 |
13 |
|
<- |
-> |
Pivot bleibt p = 7.
Suche von links liefert gr=43, da 43 größer gleich p.
Suche von rechts liefert kl=4, da 4 kleiner gleich p.
Die Suchvorgänge haben sich überkreuzt, es findet kein Austausch statt.
Aufteilung in die beiden Abschnitte.
|
7 |
4 |
43 |
58 |
29 |
64 |
13 |
|
<- |
-> |
Bearbeitung der beiden Teile nach dem gleichen Verfahren:
|
7 |
4 |
43 |
58 |
29 |
64 |
13 |
|
-> |
<- |
-> |
<- |
linke Hälfte:
Pivot p = 7.
Suche von links (-> ) liefert gr=7, da 7 größer gleich p.
Suche von rechts (<- ) liefert kl=4, da 4 kleiner gleich p.
Also wird getauscht: 7 <-> 4.
rechte Hälfte:
Pivot p = 29.
Suche von links (-> ) liefert gr=43, da 43 größer gleich p.
Suche von rechts (<- ) liefert kl=13, da 13 kleiner gleich p.
Also wird getauscht: 43 <-> 13.
|
4 |
7 |
13 |
58 |
29 |
64 |
43 |
|
<- |
-> |
-> |
<- |
linke Hälfte:
Pivot bleibt p = 7.
Suche von links (-> ) liefert gr=7, da 7 größer gleich p.
Suche von rechts (<- ) liefert kl=4, da 4 kleiner gleich p.
Die Suchvorgänge haben sich überkreuzt, es findet kein Austausch statt.
Aufteilung in die beiden Abschnitte.
rechte Hälfte:
Pivot p = 29.
Suche von links (-> ) liefert gr=58, da 58 größer gleich p.
Suche von rechts (<- ) liefert kl=29, da 29 kleiner gleich p.
Also wird getauscht: 58 <-> 29.
|
4 |
7 |
13 |
29 |
58 |
64 |
43 |
|
-> |
<- |
linke Hälfte:
fertig, da nur noch Ketten der Länge 1.
rechte Hälfte:
Pivot bleibt p = 29.
Suche von links (-> ) liefert gr=58, da 58 größer gleich p.
Suche von rechts (<- ) liefert kl=29, da 29 kleiner gleich p.
Die Suchvorgänge haben sich überkreuzt, es findet kein Austausch statt.
Aufteilung in die beiden Abschnitte.
|
4 |
7 |
13 |
29 |
58 |
64 |
43 |
|
<- |
-> |
-> |
<- |
Wir betrachten jetzt nur noch die zweite Kette mit ihrem linken und rechten Teil:
linke Hälfte:
Pivot p = 13.
Suche von links (-> ) liefert gr=29, da 29 größer gleich p.
Suche von rechts (<- ) liefert kl=13, da 13 kleiner gleich p.
Die Suchvorgänge haben sich überkreuzt, es findet kein Austausch statt.
Aufteilung in die beiden Abschnitte.
rechte Hälfte:
Pivot p = 64.
Suche von links (-> ) liefert gr=64, da 64 größer gleich p.
Suche von rechts (<- ) liefert kl=43, da 43 kleiner gleich p.
Also wird getauscht: 64 <-> 43.
|
4 |
7 |
13 |
29 |
58 |
43 |
64 |
|
<- |
-> |
linke Hälfte:
fertig, da nur noch Ketten der Länge 1.
rechte Hälfte:
Pivot bleibt p = 64.
Suche von links (-> ) liefert gr=64, da 64 größer gleich p.
Suche von rechts (<- ) liefert kl=43, da 43 kleiner gleich p.
Die Suchvorgänge haben sich überkreuzt, es findet kein Austausch statt.
Aufteilung in die beiden Abschnitte.
|
4 |
7 |
13 |
29 |
58 |
43 |
64 |
|
-> |
<- |
rechte Hälfte:
fertig, da nur noch Ketten der Länge 1.
linke Hälfte:
Pivot p = 58.
Suche von links (-> ) liefert gr=58, da 58 größer gleich p.
Suche von rechts (<- ) liefert kl=43, da 43 kleiner gleich p.
Also wird getauscht: 58 <-> 43.
|
4 |
7 |
13 |
29 |
43 |
58 |
64 |
|
<- |
-> |
Pivot p = 58.
Suche von links (-> ) liefert gr=58, da 58 größer gleich p.
Suche von rechts (<- ) liefert kl=43, da 43 kleiner gleich p.
Die Suchvorgänge haben sich überkreuzt, es findet kein Austausch statt.
Aufteilung in die beiden Abschnitte.
|
4 |
7 |
13 |
29 |
43 |
58 |
64 |
|
<- |
-> |
Es sind nur noch Teilketten der Länge 1 vorhanden, also ist das Feld sortiert.
© Ralph-Erich Hildebrandt, 18. Mai 2010