%%  Ordenamiento usando quicksort
%%  quicksort(L,R): el resultado de ordenar ascendentemente L es R
quicksort([],[]).
quicksort([X|L],R) :- partition(X,L,LT,GE),
                      quicksort(LT,SLT),quicksort(GE,SGE),
                      append(SLT,[X|SGE],R).

%% MALO:
%% quicksort([X|L],R) :- partition(X,L,LT,GE),append(LT,[X|GE],R).                      

partition(_,[],[],[]).
partition(P,[X|L],[X|LT],GE) :- X<P,partition(P,L,LT,GE).
partition(P,[X|L],LT,[X|GE]) :- X>=P,partition(P,L,LT,GE).


%% perm(L,P): P es una permutacion de L
perm([],[]).
perm([X|L1],L2) :- perm(L1,L3),insert(X,L3,L2).

%% insert(X,[],[X]).  redundante con el siguiente
insert(X,L,[X|L]).
insert(X,[Y|L],[Y|R]) :- insert(X,L,R).

%% verify(L): dada la lista ordenada L, verifica que no existe
%% una permutacion P de la lista ordenada L tal que al ordenar P no da L
verify(L) :- perm(L,P),not(quicksort(P,L)).