Beispiel

Im folgenden sei a eine Datenmenge {44, 55, 12, 42, 94, 6, 18, 67}, die aus acht Elementen des Typs Zahl besteht. Das Ziel des Beispiels ist die Veranschaulichung der oben genannten Schritte, also nicht die komplette Sortierung des Arrays, sondern der erste Teilschritt. Aus diesem lassen sich die folgenden Schritte leicht ergänzen und nachvollziehen.


 

Der erste Schritt ist die Teilung des Arrays durch Festlegung des Elements a[pivot], in diesem Falle die Zahl 42 Nun wird jeweils von links und rechts begonnen, die Elemente a[i] und a[j] mit a[pivot] zu vergleichen. Eine weitere Bedingung ist, das i kleiner oder gleich j sein muß. a[0] = 44 ist größer als a[pivot] = 42, deshalb wird der Index nicht erhöht, bis ein Element a[j] gefunden wird, welches kleiner ist als a[pivot] = 42. Das ist nicht der Fall, also wird j um eins dekrementiert. Daraus folgt:


 

a[6] = 18 ist kleiner als a[pivot] = 42, beide oben genannten Bedingungen sind also erfüllt. Die beiden Werte werden vertauscht. Das Array sieht nun folgendermaßen aus:
 

Als nächstes wird i um den Wert eins erhöht und j um einen Zähler dekrementiert, woraus sich folgendes Bild ergibt:


 

Wiederum werden die beiden Werte von a[i] und a[j] mit a[pivot] verglichen. Beide Bedingungen sind erfüllt, da a[1] = 55 größer ist als a[pivot] = 42 und a[5] = 6 kleiner als a[k] = 42. Die beiden Werte können vertauscht werden. Das Array hat jetzt folgende Einträge:


Aus der Inkrementierung von i und der Dekrementierung von j resultiert dieses Bild:
 

a[2] = 12 ist kleiner als a[pivot] = 42 und a[4] = 94 ist größer als a[k] = 42. Keine der erforderlichen Bedingungen ist erfüllt, deshalb passiert an dieser Stelle nichts. Wiederum werden die Indizes i und j erhöht, bzw. verringert:


 

Nach erneutem Vergleich der Werte ergeben sich keine Änderungen mehr, da alle drei gleich sind. Die beiden Zeiger ($a[i] / a[j]$) haben nun den gleichen Index, das heißt die Sortierung ist hier vorläufig beendet, da gilt: i darf nur kleiner oder gleich j sein. Links von a[pivot] stehen nur Zahlen, die kleiner als 42 und rechts davon nur Werte, die größer als 42 sind. Die gleiche Prozedur wird nun jeweils auf die beiden Hälften des Arrays angewandt, wobei das Element a[pivot] ausgeschlossen bleibt. Das Feld wird in immer kleinere Teile zerlegt, solange, bis nur ein einziger Wert übrig bleibt. Der nächste Teilschritt der Sortierung würde also folgendermaßen aussehen:


 

Wie man sieht, sind die beiden Hälften des Arrays abermals aufgeteilt worden. In der linken Hälfte entspricht das Element a[l] dem oben angeführten a[pivot]. Auf der rechten Seite der Aufteilung übernimmt a[m] diese Rolle. Der gesamte Sortiervorgang beginnt auf beiden Seiten getrennt voneinander von vorne, bis die letze Partition jeweils nur noch ein Element enhält. Auf eine weitere Beschreibung wird deshalb verzichtet.

Am Ende aller Sortiervorgänge ergibt sich folgendes Feld:


 

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Laufzeitkomplexität Aufwärts: Arbeitsweise Vorherige Seite: Abstrakt   Inhalt

2002-05-09