Quicksort

Prinzip

Der hier vorgestellte Quicksort nimmt das erste Element in der Eingabeliste als "Mittelwert" für das Verfahren "Divide and Conquer". Die zu sortierende Liste wird in zwei Teile aufgeteilt, diese werden rekursiv sortiert und zu einer sortierten Liste zusammengesetzt.

Code und Erklärung

Benötigt wird also zunächst eine Klausel zerlege, die eine Liste entsprechend eines Pivot-Elements zerlegt:

/* zerlege(L,X,Ks,Gs) -- Liste L wird in die Listen Ks und Gs zerlegt, wobei
                         Ks alle Elemente kleiner gleich X und Gs alle
                         Elemente größer als X enthalten */
zerlege([], X, [], []).
zerlege([Z|Zs], X, [Z|Ks], Gs) :-
  Z =< X,
  zerlege(Zs, X, Ks, Gs).
zerlege([Z|Zs], X, Ks, [Z|Gs]) :-
  Z > X,
  zerlege(Zs, X, Ks, Gs).

Der Quicksort-Algorithmus soll nun zunächst die Liste zerlegen, dann die einzelnen Listen sortieren (rekursiv) und diese (sortiert) danach wieder zusammensetzen.

quicksort([], []).
quicksort([X|Xs], Ys) :-             % X ist "Mittelwert" für Zerlegung
  zerlege(Xs, X, Ks, Gs),            % Zerlegung in zwei Teillisten
  quicksort(Ks, Ksort),              % linke Teilliste wird sortiert
  quicksort(Gs, Gsort),              % rechte Teilliste wird sortiert
  append(Ksort, [X|Gsort], Ys).      % Zusammenfügen der Teillisten mit X in der Mitte

Als Abbruchbedingung für die Rekursion dient das Faktum quicksort([],[]).