% QUICKSORT
/*

Predicado: quicksort(L,R)

  Entrada: 
    L: lista de datos 

  Salida
   R: lista ordenada de datos (orden creciente)

  Descripción 
       La lista se divide en dos partes: 
         L1: menores que la cabeza 
         L2: mayores o iguales que la cabeza

       Se aplica el método recursivamente a L1 y L2: se generan S1 y S2 (listas ordenadas)
       Se crea la solución final uniendo S1, [Cabeza] y S2

  Ejemplo 

                             5 1 4 3 2
Partir
     1 2 4 3                   | 5 |        --
  -- | 1 | 2 4 3 
           -- | 2 | 4 3   
                   3 | 4 | --
---------------------------------------------------- 
Unir
           -- | 2 | 3 4   
       -- | 1 | 2 3 4
          1 2 3 4            | 5 |        --
                           1 2 3 4 5 

*/
% Lista vacía
quicksort([],[]).

% Lista con elementos
quicksort([Cabeza|Cola],R) :-
    % Se usa la Cabeza para separar los elementos menores en L1 y los mayores o iguales en L2
	partir(Cola,Cabeza,L1,L2),
    % Se aplica el método a L1
	quicksort(L1,S1),
    % Se aplica el método a L2
	quicksort(L2,S2),
    % Se crea la solución final
	concatenar(S1,[Cabeza|S2],R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*

  Predicado auxiliar: partir(L,X,I,D).
  
  Entrada: 
    L: lista de datos 
    X: dato

  Salida
    I: lista con los elementos de L menores que X
    D: lista con los elementos de L mayores o iguales que X

  
  Descripción 
    Reparte los elementos de L en dos listas
        En I, los menores que X
        En D, los mayores o iguales que X

  Ejemplos:
    partir([1, 4, 3, 2], 5, I, D).
    I = [1 , 4, 3, 2]
    D = [] 


    partir([5, 4, 3, 2], 3, I, D).
    I = [1, 2]
    D = [5, 4] 

*/
% Lista vacía
partir([],_,[],[]):-!.

% La cabeza de la lista es menor que X
partir([Cabeza|Cola],X,[Cabeza|L1],L2) :-
    % El símbolo @ también permite comparaciones de datos no numéricos 
	Cabeza @< X,
	!,
	partir(Cola,X,L1,L2).

% La cabeza de la lista es mayor o igual que X
partir([Cabeza|Cola],X,L1,[Cabeza|L2]) :-
	partir(Cola,X,L1,L2).


/*
  concatenar(A,B,R).

  Predicado que comprueba R es la concantenación de las listas A y B

  Argumentos
  + A:
    - Significado: lista de elementos
    - Tipo: entrada y salida
  + B:
    - Significado: lista de elementos
    - Tipo: entrada y salida

  + R:
    - Significado: lista de elementos
    - Tipo: entrada y salida

  Variables locales
  + X:
    - Significado: elemento; cabeza de la lista A
  + L1:
    - Significado: lista de elementos; cola de la lista A.
  + L2:
    - Significado: lista de elementos; lista B.
  + L3:
    - Significado: lista de elementos; cola la lista R.
*/

concatenar([],L,L).

concatenar([X|L1],L2,[X|L3]):- concatenar(L1,L2,L3).
