Ordinare un elenco in Prolog

Question

Prolog ha un modo unico di gestire le cose, soprattutto perché praticamente ogni operazione comporta la ricorsione di un tipo o dell'altro.

Uno degli esempi classici di ogni lingua è l'ordinamento di un elenco di numeri interi in ordine crescente.

Che cosa è un modo ottimale (senza utilizzare troppi predicati incorporati, che preclude ovviamente un predicato sort/2) per ordinare un elenco casuale di numeri interi?

Answer 1

Il sito di programmazione Prolog di Roman Barták fornisce examples of different sort algorithms e termina con un quicksort ottimizzato.

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

Per quanto ne so i migliori algoritmi di ordinamento scritti in Prolog direttamente, senza riferimento ad alcun speciali built-in utilizzano una qualche forma di merge sort.

Un'ottimizzazione frequente consiste nell'avviare l'unione non con gli elenchi di lunghezza 1 ma con segmenti già ordinati.

Cioè, per ordinare l'elenco [4,5,3,6,2,7,1,2], le liste [4,5], [3,6], [2,7], [1,2] sarebbero fusi.

Questo può essere ulteriormente ottimizzato assemblando liste ordinate non solo in direzione ascendente, ma anche nell'altra direzione. Per l'esempio di sopra di questo significherebbe che il segmento ordinato è assemblato come segue:

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

Si noti che in Prolog è semplice per estendere la lista sia all'inizio e alla fine.

Pertanto, dobbiamo unire solo [1,2,3,4,5,6,7] e [2].

Un sistema corrente che utilizza l'implementazione originale (~ 1984) di Richard O'Keefe è Ciao-Prolog in ciao-1.15/lib/sort.pl.