Pfad:Startseite /Kurse /Leistungskurs /Rekursion /Quicksort /

Quicksort - ein schneller Sortieralgorithmus

Es soll eine Liste von Elementen (z. B. Zahlen) aufsteigend sortiert werden. Die beiden Programme erledigen diese Aufgabe. Sie sprechen für sich selbst.

Versuche die Idee durch Worte zu beschreiben.
Woran erkennt man, dass es sich um rekursive Lösungen handelt ?
Sortiere nach diesem Algorithmus die Zahlenfolge 5,3,8,1,6,9
Welche Folgen werden nicht besonders schnell sortiert ?

Pascal-Lösung

Haskell-Lösung

CONST n = ... ;
TYPE  index=1..n;
VAR   A: ARRAY[index] OF element;

PROCEDURE quicksort
           (links, rechts : index);
VAR  i,j: index;
       x: element;
BEGIN
  i:=links; j:=rechts;
  IF j>i THEN
  BEGIN
    "Bestimme x, z.B. x:=A[links]";
    REPEAT
       WHILE A[j]x DO j:=j-1;
       IF ij;
    quicksort (links, j);
    quicksort (i, rechts);
  END;
END;

quicksort [] = []
quicksort (x:xs) = quicksort kleiner
                ++ [x]
                ++ quicksort groesser
          where kleiner  = [i|i<-xs, i<=x]
                groesser = [i|i<-xs, i>x]

Motto:
Erst die Kleinen -- dann x -- dann die Großen.

nach: Duden-Informatik, BI-Wissenschaftl. Verlag,
Mannheim, Wien, Zürich 1988, Seite 480

eigene Lösung