Ordenación de listas

Teniendo en cuenta la posibilidad que ofrece la representación de listas en Prolog de acceder directamente a varios elementos del comienzo de una lista y compararlos, podemos definir un predicado ordenada/1 que determine si una lista (de números o de términos) está ordenada o no.

• El algoritmo de ordenación por inserción parte la lista en cabeza y cola, ordena la cola e inserta la cabeza en el lugar adecuado de la cola ordenada, por lo que únicamente necesita un procedimiento auxiliar para insertar elementos en listas ordenadas.

• El algoritmo de ordenación por mezcla parte la lista en dos trozos aproximadamente de igual longitud, ordena cada trozo y después los mezcla. Este algoritmo necesita dos procedimientos auxiliares: un procedimiento para separar una lista en dos aproximadamente de igual longitud y otro para mezclar listas ordenadas de forma que se obtenga una lista igualmente ordenada.

• El algoritmo de ordenación por pivote usa un elemento como pivote para partir la lista en una lista con los elementos menores o iguales que el pivote y otra con los elementos estrictamente mayores, ordena ambas listas y después las encadena los menores delante de los mayores. Este algoritmo necesita dos procedimientos: uno para separar una lista con ayuda de un pivote en dos listas una con los elementos menores o iguales que el pivote y otra con los elementos mayores, y otro procedimiento para encadenar dos listas que ya conocemos.