Bubblesort

Prinzip

Der hier vorgestellte Bubblesort funktioniert folgendermaßen: Er durchläuft die Eingabeliste im ersten Durchlauf solange bis er die erste Ungereimtheit entdeckt, wenn also ein vorhergehendes Element größer ist als das Nachfolgende, diese vertauscht er und ruft sich selber noch ein Mal auf. Dies wiederholt sich solange, bis die Liste geordnet ist.

Code und Erklärung

 geordnet([X]).
 geordnet([X,Y|Rs]):-
   X=<Y,
   geordnet([Y|Rs]).

Geordnet ist eine Liste dann, wenn sie entweder nur noch ein Element enthält oder die ersten zwei Elemente und der Rest einschließlich des zweiten Elementes geordnet ist. Diese Vorgehensweise führt unweigerlich zur Abbruchbedingung, da die Eingabeliste bei jedem Durchlauf um ein Element kleiner wird.

 bubblesort(Xs,Xs):-
   geordnet(Xs).

Der Bubblesort ist dann fertig, wenn die Eingabeliste so umgeformt wurde, dass diese geordnet ist. Dies ist auch die Abbruchbedingung für den Bubblesort.

 bubblesort(Xs,Ys):-
   append(As,[X,Y|Rs],Xs),
   X>Y, !,
   append(As,[Y,X|Rs],Xs1),
   bubblesort(Xs1,Ys).

Wenn alles Vorhergehende nicht eintrifft, gilt diese Regel. Demnach sorgen die ersten drei Aufrufe - append(As,[X,Y|Rs],Xs), X>Y, ! - dafür, dass das erste Paar X,Y gefunden wird, bei dem X größer ist als Y. Der Cut am Ende sorgt dafür, dass auch wirklich nur das erste Auftreten registriert wird, die restlichen Lösungen werden absichtlich ignoriert.

Dieses Verhalten soll hier an einem Beispiel näher gebracht werden: Es wird bubblesort([3,7,6,4],Ls). aufgerufen. An der ersten Anweisung append(As,[X,Y|Rs],Xs) angekommen, versucht Prolog das erste Paar für As,X,Y und Rs zu bestimmen, die diese Regel erfüllen, dies sieht so aus:

   Call: (8) lists:append(_L192, [_G586, _G589|_G590], [3, 7, 6, 4]) ? creep
   Exit: (8) lists:append([], [3, 7, 6, 4], [3, 7, 6, 4]) ? creep

As ist eine leere Liste, X ist 3, Y ist 7 und Rs is [6,4]. Das ist das erste Paar, das gefunden wird. Nun wird überprüft, ob X>Y ist, also:

^  Call: (8) 3>7 ? creep
^  Fail: (8) 3>7 ? creep

Dies scheint nicht der Fall zu sein, also wird die erste Regel von append erneut aufgerufen, diesmal gibt Prolog eine andere Lösung aus, die jedoch im Vergleich mit der ersten Ausgabe eine logische Folge ergibt.

   Redo: (8) lists:append(_L192, [_G586, _G589|_G590], [3, 7, 6, 4]) ? creep
   Exit: (8) lists:append([3], [7, 6, 4], [3, 7, 6, 4]) ? creep
^  Call: (8) 7>6 ? creep
^  Exit: (8) 7>6 ? creep

Hier wird positiv bestätigt, dass X > Y ist, also 7 > 6, das heißt, die Liste ist an der Stelle nicht geordnet. Der Cut sorgt dafür, dass nicht weitere Lösungen vom Aufruf der append Regel hergeleitet werden. Um der angesprochenen Fehlsortierung entgegenzuwirken, werden X und Y vertauscht ( append(As,[Y,X|Rs],Xs1) ) und zu Xs1 synthetisiert:

   Call: (8) lists:append([3], [6, 7, 4], _L196) ? creep
   Exit: (8) lists:append([3], [6, 7, 4], [3, 6, 7, 4]) ? creep

Hier setzt dann die nächste Rekursionsebene von bubblesort an, die mit Xs1 als Eingabeliste und Ys als Ergebnisliste aufgerufen wird. Irgendwann ist die Eingabeliste sortiert und die Rekursion bricht ab.