Ordenando una lista en Prolog

Question

Prolog tiene una manera única de manejar las cosas, especialmente dado que prácticamente cada operación implica la recursión de un tipo u otro.

Uno de los ejemplos clásicos que tiene cada idioma es ordenar una lista de enteros en orden ascendente.

¿Cuál es una forma óptima (sin utilizar demasiados predicados incorporados, que excluye un predicado de clasificación/2, por supuesto) para ordenar una lista aleatoria de enteros?

Answer 1

El sitio de programación de Prolog de Roman Barták da examples of different sort algorithms, que termina con una solución rápida optimizada.

quick_sort2(List,Sorted):-q_sort(List,[],Sorted). 
q_sort([],Acc,Acc). 
q_sort([H|T],Acc,Sorted):- 
    pivoting(H,T,L1,L2), 
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted) 

Answer 2

Por lo que saben los mejores algoritmos de ordenación escritos en Prolog directamente, sin hacer referencia a ningún muebles empotrados especiales utilizan algún tipo de ordenamiento por mezcla.

Una optimización frecuente es comenzar a fusionar no con listas de longitud 1 pero con segmentos ya ordenados.

Es decir, para ordenar la lista [4,5,3,6,2,7,1,2], las listas [4,5], [3,6], [2,7], [1,2] se fusionarían.

Esto se puede optimizar aún más ensamblando las listas clasificadas no solo en sentido ascendente, sino también en la otra dirección. Para el ejemplo anterior, esto significaría que el segmento según se ensambla como sigue:

[4,5|_] 
[3,4,5|_] 
[3,4,5,6|_] 
... 

Nótese que en Prolog es sencillo para extender una lista tanto en el comienzo y al final.

Por lo tanto, tenemos que fusionar [1,2,3,4,5,6,7] y [2] solamente.

Un sistema actual que utiliza la implementación original (~ 1984) de Richard O'Keefe es Ciao-Prolog en ciao-1.15/lib/sort.pl.