% Author:  Scotty Smith
% Purpose: Selection Sort

%Pre:  ToRemove is an integer
%      [Hd|Tl] is a list of integers
%      RemovedList is a list of integers
%Post: Evaluates to true if RemovedList is the second parameter list
%      with ToRemove removed from it. 
remove(_, [], []).
remove(ToRemove, [ToRemove|LstTail], RemovedList) :- RemovedList = LstTail.
remove(ToRemove, [LstHead|LstTail], RemovedList) :-
	ToRemove \= LstHead,
	remove(ToRemove, LstTail, RecRemovedList),
	append([LstHead], RecRemovedList, RemovedList).

%Pre:  AList is a list of integers
%      AListMin is an integer
%Post: Evaluates to true if AListMin is the minimum element of AList
min_helper([], _).
min_helper([AListHead|AListTail], AListMin) :-
	AListMin @=< AListHead,
	min_helper(AListTail, AListMin).

%Pre:  AList is a list of integers
%      AListMin is an integer
%Post: Evaluates to true if AListMin is the minimum element of AList
min(AList, AListMin) :-
	member(AListMin, AList),
	min_helper(AList, AListMin).

%Pre:  Alist is a list of integers
%      SortedList is the sorted Alist of integers (really a list of integers)
%Post: "Returns" true if SortedList is the sorted version of AList
selection_sort([], []).
selection_sort(Alist, [SortedHead|SortedTail]) :- min(Alist, AListMin),
	SortedHead = AListMin,
	remove(AListMin, Alist, NewAList),
	selection_sort(NewAList, SortedTail).
	
	
