quicksort([],[]).

quicksort([X|Xs],Ys) :-
  partition(Xs,X,Left,Right),
  quicksort(Left,Ls),
  quicksort(Right,Rs),
  append(Ls,[X|Rs],Ys).



/*
 partition(L,Clave,Izquierda, Derecha)
  Reparte los elementos de L en las lista Izquierda o Derecha, 
  dependiendo de si son menores o mayores que la Clave.
*/
partition([],_,[],[]).

partition([X|Xs],Y,[X|Ls],Rs) :-
  X =< Y, 
  partition(Xs,Y,Ls,Rs).

partition([X|Xs],Y,Ls,[X|Rs]) :-
  X > Y, 
  partition(Xs,Y,Ls,Rs).


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

			
leerNumeros(Resultado):- 
    read(N), 
	(
	  N \= end_of_file -> leerNumeros(Lista), Resultado = [N|Lista];
   	  true -> Resultado = []
	).

% Objetivo principal
main :- 
	write("Introduce los números (Ctrl D para finalizar)"),
	nl,
	leerNumeros(Lista),
	quicksort(Lista,Resultado),
	display(Resultado),
	nl,
	halt.
		
