quicksort

Quicksort

Funktionsweise

Quicksort geht auf den englischen Mathematiker und Informatiker Sir Charles Anthony Richard Hoare zurück, der den Algorithmus 1959 im Alter von 25 Jahren erfand. Über die Jahre wurde Quicksort in zahlreichen Varianten weiterentwickelt - das Prinzip jedoch ist geblieben.
Der Grundgedanke besteht zunächst darin, das Gesamtfeld in zwei Teilfelder zu zerlegen. Dies erfolgt durch Festlegen eines Trennelementes, das sich z.B. an der "Nahtstelle" der beiden Teilfelder befindet. Dieses Element wird als sogenanntes Pivot-Element (pivot = Drehpunkt, Drehachse) bezeichnet.
Nun werden durch Vergleich mit dem Pivot-Element Vertauschungen derart vorgenommen, dass alle Elemente, die kleiner/gleich pivot sind, im linken Teilfeld und alle Elemente, die größer/gleich pivot sind, im rechten Teilfeld gesammelt werden. Haben auf diese Weise alle Elemente ihre Ordnungsposition in Bezug auf pivot gefunden, so wird das Verfahren im linken Teilfeld durch abermaliges Teilen und Tauschen, dann wiederum im linken Teilfeld durch Teilen und Tauschen u.s.w. fortgesetzt. Wenn es nichts mehr zu teilen gibt, wird der gleiche Algorithmus auf das nächstgrößere rechte Teilfeld angewandt u.s.w. ...
In der Literatur findet sich diese Herangehensweise häufig unter der Bezeichnung "devide & conquer" (lat.: dividi et impera) - "Teile und Herrsche!".
Quicksort ist ein schönes Beispiel für einen rekursiven Algorithmus, d.h. die Prozedur ruft sich am Ende selbst wieder auf. Um nicht in eine Endlosschleife zu geraten, ist der Selbstaufruf an bestimmte Bedingungen geknüpft. Sind diese nicht erfüllt, so steigt der Algorithmus wieder aus der Rekursionstiefe empor, d.h. er nimmt sich das nächstgrößere rechte Teilfeld vor.
Die Rekursion wird verständlich, wenn man bedenkt, dass die Parameter left und right mittels "Call by value" übergeben werden. Das bedeutet, bei jedem Selbstaufruf der Prozedur wird zuvor eine Kopie der Parameter angelegt. Auf diese Weise werden left und right nicht durch sich selbst überschrieben und der Weg der Rekursionen lässt sich wieder zurückverfolgen.
Genau so gut ließe sich Quicksort aber auch iterativ umsetzen. Dabei müsste man nur dafür sorgen, dass die Parameter left und right in einem Stack (Stapel - LIFO) - also z.B. in einem dynamischen Array - gespeichert werden.

I =

J =

LEFT =

PIVOT:

RIGHT =

Stoppuhr:

Vergleiche =

Vertauschungen =


procedure quicksort(var zahl:feld; left, right: integer);
var i, j, help, pivot: integer;
begin
  i:=left;
  j:=right;
  pivot:=zahl[(left+right) div 2];
  while i<=j do
  begin
    while zahl[i]<pivot do i:=i+1;
    while zahl[j]>pivot do j:=j-1;
    if i<=j then
    begin
      if zahl[i]>zahl[j] then
      begin
        help:=zahl[j];
        zahl[j]:=zahl[i];
        zahl[i]:=help;
      end;
      i:=i+1;
      j:=j-1;
    end;
  end;
  if left<j then quicksort(zahl,left,j);
  if i<right then quicksort(zahl,i,right);
end;

procedure TForm1.btnSortClick(Sender: TObject);
begin
  quicksort(zahl,0,19);
  printList(zahl);
end;