Quick Sort in Prolog
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Quick Sort in Prolog
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin, 2009
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prolog, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DOMAINS
r=real
lr=r*
PREDICATES
qs(lr,lr)
split(r,lr,lr,lr)
split(r,lr,lr,lr,lr,lr)
split2(r,lr,lr,lr)
lconcat(lr,lr,lr)
CLAUSES
% Quick Sort
qs([],[]):-!.
qs([X],[X]):-!.
qs([H|T],R):-
% split(H,T,I,S),
split2(H,T,I,S),
qs(I,Is), qs(S,Ss),
lconcat(Is,[H|Ss],R).
% SPLIT : forward tail recursion using accumulators:
split(H, T, I, S) :- split(H, T, [], I, [], S). % change arity
split(P, [H|T], Ii, I, Si, S) :-
P>H, !, split(P, T, [H|Ii], I, Si, S); % the elements greater than the pivot P are accumulated in Ii
!, split(P, T, Ii, I, [H|Si], S). % the elements smaller than the pivot P are collected in Si
split(_, [], I, I, S, S). % at the innermost call, the accumulators are unified with the final results
% SPLIT : backward tail recursion
split2(P,[H|T],[H|TI],S):-H<=P,!,split2(P,T,TI,S).
split2(P,[H|T],I,[H|TS]):-H>P ,!,split2(P,T,I,TS).
split2(_,[],[],[]).
lconcat([H|T],L,[H|TR]):-!,lconcat(T,L,TR).
lconcat([],L,L).
]]>