Sorting a list in Prolog

Question

Prolog has a unique way of handling things, especially since practically every operation involves recursion of one sort or another.

One of the classic examples every language has is sorting a list of integers into ascending order.

What is an optimal way (without using too many built-in predicates, which precludes a sort/2 predicate, of course) to sort a random list of integers?

Solution 1

Roman Barták's Prolog Programming site gives examples of different sort algorithms, ending with an optimized quicksort.

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)

Solution 2

As far as I know the best sorting algorithms written in Prolog directly, without reference to any special built-ins use some form of merge sort.

A frequent optimization is to start merging not with lists of length 1 but with already sorted segments.

That is, to sort the list [4,5,3,6,2,7,1,2], the lists [4,5],[3,6],[2,7],[1,2] would be merged.

This can be optimized even further by assembling sorted lists not only in ascending direction, but also in the other direction. For the example above this would mean that the sorted segment is assembled as follows:

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

Note that in Prolog it is straight forward to extend a list both in the beginning and at the end.

Thus, we have to merge [1,2,3,4,5,6,7] and [2] only.

A current system that uses the original implementation (~1984) of Richard O'Keefe is Ciao-Prolog in ciao-1.15/lib/sort.pl.

Comments

[gusbro]

Just a note: that predicate (using the pivoting/4 implemented in your link) performs a descending sort, you have to reverse the comparison operators of pivoting/4 to perform an ascending sort.

[false]

@j4nbur53: Download the current version of Ciao.

[Admin]

My favorite are trees for sorting, see also stackoverflow.com/questions/3270543/… , but Prolog trees involve more copying than Java trees.