Quicksort die Idee

31.2 Quicksort
31.2.1 Die Idee

Quicksort

Der Quicksort-Algorithmus wurde zu Beginn der Sechziger Jahre von A. C. R. Hoare erfunden. Auf einem Rechner impelmentiert wurde dieser Algorithmus allerdings erst, als rekursives Programmieren möglich wurde. Der Algorithmus ist sehr effizient und sortiert eine Folge von Elementen durch rekursives Teilen. Was damit gemeint ist, soll ein Beispiel zeigen: Wir beschränken uns zunächst auf Folgen von 10 Zahlen vor, die in einer Liste die Plätze 0 bis 9 belegt..

Im ersten Schritt des Qicksort bestimmt man aus der Liste zunächst eine Zahl als so genannten Trenner (Angelpunkt engl. pivot), z.B. die Zahl 60 auf Platz der Nr. 4.

Der Name Trenner rührt daher, dass er benutzt wird, aus der Liste zwei Teillisten so zu erzeugen. Dabei werden Teillisten so konstruiert, dass in der linken Teilliste nur Zahlen stehen, die kleiner als der Trenner, und damit kleiner 60 sind. Die Zahlen, die größer als der Trenner, und damit größer als 60 sind, finden in der rechten Teilliste ihren Platz. Der Trenner selbst gehört dann zu keiner Teilliste mehr.

Nach dem Aufteilen in zwei Teillisten hätte unsere Liste die folgende Gestalt:

Es sei darauf aufmerksam gemacht, dass der Trenner seinen Platz in der sortierten Liste bereits jetzt eingenommen hat. Mit den beiden Teillisten verfahren wir auf die gleiche Weise wie mit der Ausgangsliste.

				60
49	7	58	41		88	82	77	76	86
7	49	58	41		76	77	82	88	86

In den Zeilen der oben dargestellten Tabelle sind die Einträge in der Liste so eingetragen, dass der Sortiervorgang etwas deutlicher wird. So stehen in der ersten Zeile die bereits sortierte Elemente, es sind die Elemente, die schon einmal Trenner waren. In der zweiten Zeile sind die Trenner der neuen Teillisten für den nächsten Schritt markiert. In der dritten Zeile schließlich erkennt die Teillisten der „nächsten Generation“.

7				60		77
	49	58	41		76		82	88	86
	49	41	58		76		82	86	88

Enthält eine Liste nur noch ein Element, dann ist sie a priori sortiert

7			58	60	76	77			88
	49	41					82	86
	41	49					82	86

7		49	58	60	76	77	82		88
	41							86
	41							86

7	41	49	58	60	76	77	82	86	88

Wir sind am Ende angekommen, wenn die Teillisten nur noch ein Element enthalten.

Es bleiben zwei Fragen.
Erstens, wie findet man überhaupt den Trenner? Zweitens, mit welchem Algorithmus erzeugt man die beiden Teillisten, wenn man den Trenner gefunden hat? Die erste Frage lässt sich einfach beantworten: Man sieht leicht ein, dass das Verfahren unabhängig ist vom Wert des Trenners. Allerdings, wird der Algorithmus am effizientesten, wenn die entstehenden Teillisten in etwa gleichgroß sind. Gehen wir davon aus, dass die Listen gut durchmischt sind. Dann genügt es die Zahl als Trenner zu wählen, die auf dem Platz in der Mitte steht. Dies ist einfach bei ungerader Anzahl der Listenelemente. Ist die Anzahl dagegen gerade, denkt man sich die Liste in zwei gleichgroße Teillisten zerlegt und wählt das am weitesten rechts stehende Element in der linke Liste. Man mache sich klar, dass mit

Trenner finden

pivot =liste[((untereGrenze+obereGrenze) / 2)];

wegen der Ganzzahldivision „pivot“ in beiden Fällen der Trenner ist. (Die ganze Liste ist wieder als Reihung realisiert und hat dabei den Namen „liste“. Die ganze Liste, aber auch jede Teilliste wird dann über Platznummern „obereGrenze“ und „untereGrenze“ festgelegt.

Erzeugen der Teillisten

Kommen wir zu der schwierigeren Frage: Wie erzeugt man die beiden Teillisten? Wie erklären den Algorithmus an der gleichen Ausgangsliste. Die Variablen „links“ und „rechts“ zeigen zunächst wie untereGrenze (uG) und obereGrenze (oG) auf Anfang bzw. Ende der Reihung.

links = untereGrenze;
rechts= obereGrenze;

(Anmerkung: Beim ersten Aufruf des Trennens der Urliste müssen untereGrenze und obereGrenze auf 0 bzw. auf liste.length-1 gesetzt werden)

67	7	58	88	60	41	82	77	49	86
uG links									oG rechts

links wandert nun solange nach rechts, bis seine Zelle eine Zahl enthält, die größer ist als pivot. rechts wandert solange nach links, bis seine Zelle eine Zahl enthält, die kleiner ist als pivot.

while {
(liste[links]<pivot) links++;
}

bzw

while {
(pivot < liste[rechts]) rechts--;
}

76	7	58	88	60	41	82	77	49	86
uG links									oG rechts

links und rechts tauschen nun ihre Zelleninhalte aus. .

49	7	58	88	60	41	82	77	76	86
uG			links		rechts				oG

links und rechts wandern weiter bis zu den nächsten Tauschpositionen und übergehen dabei Zellen, deren Inhalte sch bereits in den richtigen Teillisten befinden. Beobachten wir bereits in unsere Liste unmittelbar vor. Nach dem nächsten Tausch sieht die Liste so aus:

49	7	58	41	60	88	82	77	76	86
uG			links		rechts				oG

Das "Wandern" von „links“ und „rechts“ hat dann ein Ende, wenn „rechts“ links von „links“ steht. Das Erzeugen der Teillisten für den Trenner 60 ist fertig:

49	7	58	41	60	88	82	77	76	86
uG			rechts		links				oG

Die linke Teilliste ist durch die Positionen uG und rechts, die rechte Teilliste durch die Positionen links und oG festgelegt. Das Sortieren dieser neuen Teillisten erfolgt durch den rekursiven Aufruf des Algorithmus mit den neuen Grenzen als Übergabeparameter.

if (untereGrenze < rechts) {
quickSort(liste, untereGrenze, rechts); bzw.
}
if (links < obereGrenze) {
quickSort(liste, links,obereGrenze);

In der if-Klausel steckt die Abbruchbedingung für den rekursiven Abstieg. Ist nämlich obereGrenze == rechts bzw. links == untereGrenze, so enthalten die Listen nur noch ein Element und sind somit a priori sortiert.

Zusammenfassung

In einer Vorstufe zur Normsprache lässt sich der Algorithmus gut auf den Punkt bringen:

Sortiere(Liste, von bis):
   wenn (bis > von) tue:
       partitioniere die Liste um das Pivot-Element
       (bei Index p) herum
   Sortiere(Liste,von,p-1)
   Sortiere(Liste,p+1,bis)

Der wesentlich Punkt dabei ist die Forderung, dass nach dem Partitionieren alle Elemente links vom pivot KLEINER (oder GLEICH) sind als dieser, und alle Elemente rechts davon GRÖSSER (oder gleich).

31.2.2 Implementierung

zur Startseite