Selection sorting.
Remember that selection sort works by
finding the smallest element and moving it into the first position,
then finding the second smallest and moving it into the second
position. In general, on the ith iteration, it finds the ith smallest
element and move it to position i. This works as follows:
(selection '(6 4 5 3 9 3))
(cons 3 (selection '(6 4 5 9 3))
(cons 3 (cons 3 (selection '(6 4 5 9))
(cons 3 (cons 3 (cons 4 (selection '(6 5 9))
(cons 3 (cons 3 (cons 4 (cons 5 (selection '(6 9))
(cons 3 (cons 3 (cons 4 (cons 5 (cons 6 (selection '(9))
(cons 3 (cons 3 (cons 4 (cons 5 (cons 6 (cons 9 (selection '())
Which becomes (3 3 4 5 6 9).
The scheme code below does exactly this:
/* put the smallest element at the front of the current list
call selection on the list minus the smallest element
*/
selectionsort([],[]).
selectionsort([First|Rest], [Smallest|SortedList]) :-
smallest(Rest, First, Smallest),
remove([First|Rest], Smallest, NewList),
selectionsort(NewList, SortedList).
/* looks for the smallest element in the list
atom A is the current smallest
*/
smallest([], Smallest,Smallest).
smallest([First|Rest], CurrSmallest, Smallest) :-
First < CurrSmallest, smallest(Rest, First, Smallest).
smallest([_|Rest], CurrSmallest, Smallest) :-
smallest(Rest, CurrSmallest, Smallest).
/* remove the first occurance of atom A from L */
remove([], _, []).
remove([First|Rest], First, Rest).
remove([First|Rest], Element, [First|NewList]) :-
remove(Rest, Element, NewList).
test(Y,X) :- remove([5,3,67,5,1,8,9], Y, X).
/*
?- consult('selection.pl').
?- selectionsort([11,23, 0,42,18,90, 1],X)
?- smallest([11,23,0,45,8], 5, What).
?- remove([11,23, 0,42,18,90, 1],18,NewList).
*/
Merge Sort
Mergesort divides the list in half everytime,
calling itself on each half. As the recursion unwinds, it merges the
sorted list into a new
sorted list. For example, assume we have the following:
(mergesort '(6 4 5 7 8 9 3 4))
/ \
(mergesort '(6 4 5 7)) (mergesort '(8 9 3 4))
/ \ / \
(mergesort '(6 4)) (mergesort '(5 7)) (mergesort '(8 9)) (mergesort '(3 4))
At the lowest tree leves, the two element get sorted and the recursion unwinds.
(mergesort '(6 4 5 7 8 9 3 4))
/ \
(mergesort '(6 4 5 7)) (mergesort '(8 9 3 4))
/ \ / \
(4 6) (5 7) (8 9)) (3 4))
The next level of recursion:
(mergesort '(6 4 5 7 8 9 3 4))
/ \
(4 5 6 7)) (3 4 8 9)
/ \ / \
(4 6) (5 7) (8 9)) (3 4))
And the final level with merges into the overall list
(3 4 4 5 6 7 8 9)
/ \
(4 5 6 7) (3 4 8 9)
Of course, this is not the actual order that things happen but it give
the overall algorithm flavor.
In scheme, we can write functions to split lists, and merge sorted
lists. Once we have these, the mergesort itself is fairly short.
mergesort([],[]).
mergesort([OneElement], [OneElement]).
mergesort([OneElement,SecondElement], SortedList) :-
mergelists([OneElement],[SecondElement], SortedList).
mergesort([FirstLis|RestLis], SortedList) :-
split([FirstLis|RestLis],[FirstSplitLis,RestSplitLis]),
mergesort(FirstSplitLis, SortedFirstLis),
mergesort(RestSplitLis, SortedRestLis),
mergelists(SortedFirstLis, SortedRestLis, SortedList).
mergelists([], M, M).
mergelists(Lis, [], Lis).
/* assume L and M are sorted lists*/
mergelists([FirstLis|RestLis], [FirstM|RestM], [FirstLis|RestLisMerged]) :-
FirstLis < FirstM,
mergelists(RestLis, [FirstM|RestM], RestLisMerged).
mergelists([FirstLis|RestLis], [FirstM|RestM], [FirstM|RestMMerged]) :-
mergelists([FirstLis|RestLis], RestM, RestMMerged).
/* extract elements start to stop into a list */
sublist([],_,_,_,[]).
sublist([_|RestLis], Start, Stop, Ctr, SubList) :-
Ctr < Start,
NextCtr is Ctr + 1,
sublist(RestLis, Start, Stop, NextCtr, SubList).
sublist(_, _, Stop, Ctr, []) :-
Ctr > Stop.
sublist([FirstLis|RestLis], Start, Stop, Ctr, [FirstLis| SubList]) :-
NextCtr is Ctr + 1,
sublist(RestLis, Start, Stop, NextCtr, SubList).
/* split the list in half:, ; returns ((first half)(second half)) */
split([], [[],[]]).
split([OneElement],[[OneElement],[]]).
split(Lis, [SubLis1,SubLis2]) :-
length(Lis,Len),
HalfLen is Len//2,
HalfLenPlus is HalfLen + 1,
sublist(Lis,1,HalfLen, 1, SubLis1),
sublist(Lis, HalfLenPlus, Len, 1, SubLis2).
/*
?- consult('mergesort.pl').
?- mergesort([2, 11,1],X).
X = [1, 2, 11]
?- mergesort([11, 1, 8, 28, 50, 2,4,15],X).
X = [1, 2, 4, 8, 11, 15, 28, 50]
?- mergelists([1,3,5,7], [2,4,6,45,95], X).
X = [1, 2, 3, 4, 5, 6, 7, 45, 95]
?- sublist([3,4,5,6], 0,1,0,X).
X = [3, 4]
?- sublist([3,4,5,6], 1,1,0,X).
X = [4]
?- sublist([3,4,5,6], 1,4,0,X).
X = [4, 5, 6]
?- split([1,2,3,4,6,7,8],X).
X = [[1, 2, 3], [4, 6, 7, 8]]
*/