CODEWITHSUNDEEP
listsortingprolog
Raceimaztion
Raceimaztion

Reputation: 9624

Sorting a list in Prolog

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?

Upvotes: 14

Views: 48764

Answers (2)

dommer
dommer

Reputation: 19810

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)

Upvotes: 9

false
false

Reputation: 10102

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.

Upvotes: 6

Related Questions