% 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]).