28.2 Quicksort
28.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..

 
76 7 58 88 60 41 82 77 49 86
 

Im ersten Schritt des  Qicksort bestimmt man aus der Liste zunächst eine Zahl als so genannten Trenner (Angelpunkt, Drehpunkt 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:

 
49 7 58 41 60 88 82 77 76 86
 

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).
 

divide and
conquer
Die Effizienz des Algorithmus beruht darauf, dass man das Problem, hier das Sortieren einer Liste, teilt, also die Liste 'halbiert' und dies sortiert, wobei das Halbieren und Teilsortieren rekursiv geschieht. Algorithmen, die nach diesem Muster konstruiert sind, nennt man 'teile und herrsche'-  oder auf engl. 'divide and conquer' - Algorithmen. Wir werden die Effizienz der Algorithmen experimentell und später analytisch untersuchen.
 
zu 28.2.2 Implementierung
zur Startseite www.pohlig.de  (C) MPohlig 2006