%DCC-FCUP - Logica e Programacao 2010-2011

:-[-listas].

slowsort(X,Y) :-  perm(X,Y), sorted(Y).

sorted([]).
sorted([X]).
sorted([X,Y|Z]) :- X=<Y, sorted([Y|Z]).

perm([],[]).
perm([X|Y],[U|V]):- delete(U,[X|Y],Z), perm(Z,V).

delete(X,[X|Y],Y).
delete(X,[Y|Z],[Y|Z1]):- delete(X,Z,Z1).

%insert sort

inssort([],[]).
inssort([X|Xs],Ys):- inssort(Xs,Zs), insert(X,Zs,Ys).

insert(X,[],[X]):-!.
insert(X,[Y|Ys],[Y|Zs]):-X>Y, !, insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]):- X=<Y.

%quick sort

qsort([],[]).
qsort([X|Xs],Ys):-
partition(Xs,X,L,B),
qsort(L,Ls),
qsort(B,Bs),append(Ls,[X|Bs],Ys).

partition([],X,[],[]).
partition([X|Xs],Y,[X|Ys],Bs):- X=<Y, !, partition(Xs,Y,Ys,Bs).
partition([X|Xs],Y,Ys,[X|Bs]):- X>Y, partition(Xs,Y,Ys,Bs).
