selection_sort.pg

% Finds min between two numbers.
min_nums(X,Y,X) :- X =< Y.
min_nums(X,Y,Y) :- Y =< X.

% Finds min of list.
% Obviously, if there's only one item, then that's the minimum.
min([Item|[]],Item).
% If there's more than one item, find the minimum of the tail,
% then take the minimum of the tail's minimum and the head element.
min([Head|Tail],Min) :-
    min(Tail, PossibleMin),
    min_nums(Head, PossibleMin, Min).

% Deletes element from list exactly once if it is in the list.
% Obviously, don't delete anything from empty list.
delete_once([],_,[]).
% If you find Elem, then you are left with just the Tail.
delete_once([Elem|Tail],Elem,Tail).
% If the head element is not Elem,
% then add it to the result and keep looking for Elem.
delete_once([Head|Tail],Elem,[Head|Result]) :-
    \+ Head is Elem,
    delete_once(Tail,Elem,Result).

% Implements selection sort algorithm.
% Obviously, empty list is already sorted.
selection_sort([],[]).
% Add the minimum to the result, delete it from the array,
% and then sort the resulting array.
selection_sort(Arr, [Min|Result]) :-
    min(Arr, Min),
    delete_once(Arr, Min, Arr2),
    selection_sort(Arr2, Result).