Insertionsort

Prinzip

In dem hier in Prolog realisierten Insertionsort wird eine eingegebene Liste solange von vorne zerlegt, bis sie leer ist ("[]"). Danach wird in den Rekursionsebenen wieder zurückgesprungen und die davor abgespaltenen Elemente werden in richtiger Reihenfolge in die Ergebnisliste eingefügt.

Code und Erklärung

insertionsort([], []).
insertionsort([K|Rs], Ys) :-
  insertionsort(Rs, Zs),            % sortieren der Restliste
  einfuegen(K, Zs, Ys).             % K in bisherige Liste einfügen

Wie weiter oben bereits erwähnt, gilt als Rekursionsende der Fall, dass die Eingabeliste leer ist. Dies kann dadurch eintreten, dass entweder der Benutzer eine leere Liste eingibt oder der im oberen Absatz dargestellte Algorithmus die Köpfe der Eingabeliste solange abgespalten hat, bis diese leer ist.

Benötigt wird nun hier ein Prädikat einfuegen, welches ein Element X an der "richtigen" Stelle in einer Liste einfügt.

einfuegen(X, [], [X]).
einfuegen(X, [Y|Rs], [X,Y|Rs]) :-   % X ist kleinstes Element
  X =< Y.
einfuegen(X, [Y|Rs], [Y|Zs]) :-     % X ist größer als Kopf der Liste
  X > Y,
  einfuegen(X, Rs, Zs).             % X in Restliste einsortieren