Selectionsort

Aus Informatik
Wechseln zu: Navigation, Suche

Prinzip

Der Selectionsort findet in der ihm übergebenen Liste das kleinste Element, löscht es aus der eingegebenen Liste und schreibt es in die Ausgabeliste. Somit wird die Eingabeliste im Laufe des Algorithmus immer kleiner, das Ende ist damit entweder eine leere Eingabeliste oder eine einelementige Liste. Letzteres bietet sich jedoch mehr an, da man dadurch eine weitere Rekursionsstufe spart.

Code und Erklärung

selectionsort([X], [X]).
selectionsort(Xs, [Min|Rs]) :-
  mini(Xs, Min),
  geloescht1(Min, Xs, Ys),
  selectionsort(Ys, Rs).

Wie oben erwähnt ist das Ende der Rekursion eine einelementige Eingabeliste, dieser entspricht eine einelementige Ausgabeliste mit dem selben Element [X]. Für alle anderen Fälle wird die Regel selectionsort(Xs,[Min|Rs]) aufgerufen. Diese bestimmt das Minimum - mit der Regel mini - aus der Eingabeliste Xs und setzt es als Kopf vor die Ausgabeliste. Ferner löscht es das erste Aufkommen dieses Minimums in der Eingabeliste - mit der Regel geloescht1. Und ruft sich am Ende selber auf, dies führt unweigerlich dazu, dass die Eingabeliste irgendwann einelementig wird, sofern dies nicht zu Beginn der Fall war, und das erste Faktum gematcht werden kann.

Bleiben noch die Regeln mini und geloescht1, welche aus früheren Aufgaben schon bekannt sein sollten.

% mini(Ls,Min) bedeutet: Min ist das Minimum der Liste Ls
mini([M], M).
mini([K|Rs], K) :-
  mini(Rs, M),
  K = <M.
mini([K|Rs], M) :-
  mini(Rs, M),
  K > M.

% geloescht1(X,Ls,Ms) bedeutet: Ms entsteht aus Ls durch einmaliges Löschen von X 
geloescht1(_, [], []).
geloescht1(X, [X|Rs], Rs).
geloescht1(X, [Y|Rs], [Y|Qs]) :-
   X \= Y,
   geloescht1(X, Rs, Qs).