- Insertion sort:
insertionsort([],[]).
insertionsort([First|Rest], SortedList) :-
insertionsort(Rest,NewList),
insert(First, NewList, SortedList).
insert(Element, [], [Element]).
insert(Element, [First|Rest], [First|NewList]) :-
Element > First, insert(Element, Rest, NewList).
insert(Element, List, [Element|List]).
test(Y,X) :- insert(Y, [5,3,67,5,1,8,9], X).
/*
?- consult('insertion.pl').
?- insertionsort([11,23, 0,42,18,90, 1],X)
?- insert([1,2,10,45], 15, What).
*/
- List flattening
flatten([], []).
flatten([First|Rest], [First|RestFlattened]) :-
atomic(First),
flatten(Rest, RestFlattened).
flatten([First|Rest], FlattenedList) :-
flatten(First, FirstFlattened),
flatten(Rest, RestFlattened),
append(FirstFlattened, RestFlattened, FlattenedList).
append([],List, List).
append([First|Rest], List2, [First|List3]) :-
append(Rest, List2, List3).
/*
?- consult('flatten.pl').
?- flatten([1,2,3], X).
X = [1, 2, 3]
?- flatten([1,[2,3]], X).
X = [1, 2, 3]
?- flatten([1,[[2,3]]], X).
X = [1, 2, 3]
?- flatten([1,[[[[2]],3]]], X).
X = [1, 2, 3]
*/
- Partition function for quicksort
partition([First|RestLis], PartionedList) :-
part(RestLis, First, PartionedList).
/* #((<= part) part (> part)) will be returned */
part([], Pivot, [[],Pivot,[]]).
/*recursive call which will return a list with structure ( (<= pivot) pivot (> pivot)) */
part([First|Rest], Pivot, [R1,Pivot,[First|R3]]) :-
First > Pivot,
part(Rest, Pivot, [R1,_,R3]).
part([First|Rest], Pivot, [[First|R1]|R3]) :-
part(Rest, Pivot, [R1|R3]).
append([],List, List).
append([First|Rest], List2, [First|List3]) :-
append(Rest, List2, List3).
/*
?- consult('quicksort.pl').
?- part([11, 1, 8, 28, 50, 2,4,15],10,X).
X = [[1, 8, 2, 4], 10, [11, 28, 50, 15]]
?- partition([11, 1, 8, 28, 50, 2,4,15],X).
X = [[1, 8, 2, 4], 11, [28, 50, 15]]
*/
Now, using the above partition function, try to write quicksort. A
soln is here but don't look until you have tried it!