% BURBUJA
/*
 Predicado: burbuja(L,R)

 Entrada:
   L: lista de datos 

  Salida
   R: lista ordenada de datos (orden creciente)

  Descripción 
       En cada paso, se coloca el elemento más pequeño al princio de la lista.
  
  Ejemplo

  Ordenado    | No ordenado
              | 5 4 1 3 2
  1           | 5 4 2 3
  1 2         | 5 4 3
  1 2 3       | 5 4
  1 2 3 4     | 5
  1 2 3 4 5   | 

*/

% Lista vacía.
burbuja([],[]):-!.

% Lista no vacía
burbuja(L,[P|Ordenada]):-
        traer_minimo(L,[P|Cola]),
        burbuja(Cola,Ordenada).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

/*
  Predicado auxiliar: traer_minimo(L,R).

  Entrada:
    L: lista de datos 

  Salida
    R: lista de datos donde el primero es el menor.
  
  Descripción: empezando por el final de la lista, se van intercambiando los datos hasta colocar el menor al principio.

   No explorado | Explorado 
   5  4  1  3 2 | 
   5  4  1  3   | 2   
   5  4  1      | 2 3
   5  4         | 1 2 3   
   5            | 1 4 2 3
                | 1 5 4 2 3
*/

% Lista vacía
traer_minimo([],[]):-!.

% Lista con un elemento
traer_minimo([X],[X]):-!.

% Lista con dos elemento: el segundo es menor que el primero
% El símbolo @ también permite comparaciones de datos no numéricos 
traer_minimo([X,Y],[Y,X]) :-    Y @< X, !.

% Lista con dos elementos: el primero es menor o igual que el segundo 
traer_minimo([X,Y],[X,Y]):-!.

% Lista con más de dos elementos
traer_minimo([X,Y|Cola], L) :-
  % Se  obtiene el menor M a partir del segundo elemento
        traer_minimo([Y|Cola],[M|Resto]),
  % Se compara M con el primer elemento de la lista 
  % El símbolo @ también permite comparaciones de datos no numéricos 
        (
         X @=< M -> L = [X,M|Resto];
         X @> M  -> L = [M,X|Resto]
        ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% INSERCION

/* 
  Predicado: insercion(L,R)

  Entrada: 
    L: lista de datos 

  Salida
   R: lista ordenada de datos (orden creciente)

  Descripción 
       Se va ordenando la lista por el final.
       El último elemento de la parte sin ordenar se inserta en la parte ordenada

  Ejemplo    
  
  No ordenado | Ordenado
  5 4 1 3 2   |   
  5 4 1 3     | 2
  5 4 1       | 2 3
  5 4         | 1 2 3
  5           | 1 2 3 4
              | 1 2 3 4 5

*/

% Lista vacía
insercion([],[]):-!.

% Lista con un elemento
insercion([X],[X]):-!.

% Lista con dos o más elementos
insercion([Cabeza|Cola],R) :-
  % Se ordena la Cola
        insercion(Cola, Cola1),
  % Se inserta la Cabeza de la lista en la cola ordenada
        insercion_ordenada(Cola1,Cabeza,R).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*
  Predicado auxiliar: insercion_ordenada(L,X,R)

  Entrada:
    L: lista ordenada de datos (orden creciente)
    X: dato

  Salida:
    R: nueva lista en la que se ha insertado X de forma ordenada en L 


  Ejemplo    
   X = 3

  menores | X | 
          | 3 | 1 2 4 5
        1 | 3 | 2 4 5
      1 2 | 3 | 4 5 
*/

% Inserción ordenada en una lista vacía
insercion_ordenada([],X,[X]):-!.

% Inserción ordenada de X en una lista no vacía: la cabeza de la lista es menor que X
insercion_ordenada([Cabeza|Cola],X,[Cabeza|R]) :-
  % El símbolo @ también permite comparaciones de datos no numéricos 
        Cabeza @< X,
        !,
        insercion_ordenada(Cola,X,R).

% Inserción ordenada de X en una lista no vacía: la cabeza de la lista es mayor que X
insercion_ordenada([Cabeza|Cola],X,[X,Cabeza|Cola]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MERGESORT
/*
 Predicado: mergesort(L,R)

  Entrada: 
    L: lista de datos 

  Salida
   R: lista ordenada de datos (orden creciente)

  Descripción 
     Split
       Los datos de lista se distribuyen en dos partes de forma alternativa.
       El proceso se repite de forma recursiva 
       hasta que la lista esté compuesta por sublistas con un elemento.
     Merge
       A continuación, se van uniendo de forma ordenada las sublistas de dos en dos. 
         
  Ejemplo 
                [5 4 1 3 2]
Split
            [5 1 2]   |     [4 3]
       [5 2]   | [1]  ||  [4] | [3]
  [5]    | [2] || [1] ||| [4] | [3]

Merge
  [2 5]  | [1] || [ 3 4] 
      [1 2 5]  || [ 3 4] 
          [1 2 3 4 5] 

*/
% Lista vacía
mergesort([],[]):-!.

% Lista con un elemento.
mergesort([A],[A]):-!.

% Lista con dos o más elementos
mergesort([A,B|Cola],S) :-  
   % Se separan los elementos de la lista en dos sublistas
   split([A,B|Cola],L1,L2),
   % Se aplica la recursión a la primera lista
   mergesort(L1,S1),
   % Se aplica la recursión a la segunda lista 
   mergesort(L2,S2),
   % Se unen las listas resultantes
   merge(S1,S2,S).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*

  Predicado auxiliar: split(L,I,D).
  
  Entrada: 
    L: lista de datos 

  Salida
    I: lista con los elementos de L que ocupan un lugar impar
    D: lista con los elementos de L que ocupan un lugar par

  
  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, 2, 3, 4], I, D).
    I = [1, 3]
    D = [2, 4] 


    partir([a, b, c, d], I, D).
    I = [a, c]
    D = [b, d] 

*/

% Lista vacía
split([],[],[]):-!.

% Lista con un elemento
split([A],[A],[]):-!.

% Lista con dos o más elementos
split([A,B|Cola],[A|ColaI],[B|ColaD]):- split(Cola,ColaI,ColaD).



/*

  Predicado auxiliar: merge(I,D,R).
  
  Entrada: 
    I: lista con datos ordenados
    D: lista con datos ordenados
    
  Salida
         R: lista de datos con datos ordenados

  
  Descripción 
    Una los datos de las lista I y D en L

  Ejemplos:
    merge([1, 3], [2, 4],R).
    R= [1, 2, 3, 4]
    
    merge([ a, b, d], [c], R).
    R = [a, b, c, d]
*/


% La segunda lista está vacía
merge(I,[],I):-!.

% La primera lista está vacía
merge([],D,D):-!.

% La cabeza de la primera lista es menor que la cabeza de la segunda lista
merge([A|ColaI],[B|ColaD],[A|Cola]):-  
        % El símbolo @ también permite comparaciones de datos no numéricos  
        A @=< B, 
        !,
        merge(ColaI,[B|ColaD],Cola).

% La cabeza de la segunda lista es menor o igual que la cabeza de la primera lista
merge([A|ColaI],[B|ColaD],[B|Cola]):-  
        % El símbolo @ también permite comparaciones de datos no numéricos 
        A @> B,  
        merge([A|ColaI],ColaD,Cola).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 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).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% SELECCION
/*
  Entrada: 
    L: lista de datos 

  Salida
   R: lista ordenada de datos (orden creciente)

  Descripción 
       En cada paso, el elemento mínimo de la parte sin ordenar (parte final) se coloca en la parte ordenada (parte inicial) de la lista.
  
  Ejemplo    

        Ordenado  | No ordenado 
                | 5 1 4 3 2
        1         | 5 4 3 2
        1 2       | 5 4 3
        1 2 3     | 5 4
        1 2 3 4   | 5
        1 2 3 4 5 |

*/

% Lista vacía
seleccion([],[]):-!.

% Lista con elementos
seleccion(Lista, [Min|Cola]) :-
  % Se obtiene el mínimo 
        minimo(Lista,Min),
        % Se borra (une vez) el mínimo de la lista
        borrar(Min, Lista, Lista1),
        % Se ordena el resto de la lista
        seleccion(Lista1, Cola).
        % La solución final se construye en el parámetro de salida: [Min|Cola]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*
  Predicado auxiliar: borrar(X,L,R)

  Entrada: 
    X: datos
    L: lista de datos 

  Salida
   R: lista de datos sin la primera aparición de X en L

  Descripción
   Borra el elemento X de una lista: solamente se borra la primera aparición de X

  Ejemplo
   ?- borrar(3,[1,2,3,4,3,1],R).
      R = [1, 2, 4, 3, 1].
*/
% Lista vacía
borrar(_,[],[]):-!.

% El elemento a borrar se encuentra en la cabeza de la lista
borrar(X,[X|Cola],Cola):-!.

% El elemento a borrar no se encuentra en la cabeza de la lista
borrar(X,[Y|Cola1],[Y|Cola2]):- 
  !,
        borrar(X,Cola1,Cola2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*
   Predicado auxiliar: minimo(L,R)

  Entrada: 
    L: lista de datos no vacía

  Salida
    R: mínimo de L

  Descripción
     Obtiene el mínimo de una lista no vacía

  Ejemplo
   ?- minimo([5,4,1,3,2],R).
      R = 1
*/
% Lista con un elemento
minimo([X],X):-!.

% Lista con más de elemento: 
minimo([X|Cola],Minimo) :- 
  % Se obtiene el mínimo de la cola: Y
        minimo(Cola,Y),
        % Se compara Y con el primero elemento X de la lista
  % El símbolo @ también permite comparaciones de datos no numéricos 
        (
                        X @=< Y -> Minimo = X;
                        true    -> Minimo = Y  
        ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% CARGAR LISTA
      
cargar_lista(L) :-
        write('Introduce los datos que se van a ordenar (CTRL-D para finalizar) -->'),
        read(X),
       (
        X == end_of_file, L = [];       
        cargar_lista(R),
        append([X],R,L)
       ).

% MENU
  
menu :-
        cargar_lista(R),
        nl,
        write('La lista de datos que se van a ordenar es: '),
        write(R),
        nl,
        repeat,
        write('Elija un metodo de ordenacion'),nl,
        write('1) Burbuja'),nl,             
        write('2) Mergesort'),nl,              
        write('3) Quicksort'),nl,              
        write('4) Insercion'),nl,               
        write('5) Seleccion'),nl,               
        read(Op),
        (
                Op =:= 1 -> burbuja(R,S);
                Op =:= 2 -> mergesort(R,S);
                Op =:= 3 -> quicksort(R,S);
                Op =:= 4 -> insercion(R,S);
                Op =:= 5 -> seleccion(R,S);
                true -> write('opcion incorrecta '), write(Op), nl, fail
        ),
        write('La lista ordenada es:'),nl,
        write(S).

