0

I am trying to figure out how sort/2 is implemented in Prolog. I would like to see how it works but I cannot find the code for it anywhere. Does somebody know how it is implemented?

Improve this question
2
  • Does this answer your question? Sorting a list in Prolog Commented Dec 11, 2020 at 22:10
  • What I would like to do is sort by the second element in decending order without removing dublicates. I have at the moment done it like "sort4(List, Sorted) :- sort(2, @>=, List, Sorted)." however i am not allowed to use anything else then sort/2 so I am thought I could change the original function and implement that as a helper function. Commented Dec 12, 2020 at 20:13

4 Answers 4

Reset to default
2

In SWI-Prolog, sort/2 is a "built-in", so it's in C.

The file seems to be src/pl-lists.c of the distribution.

Here it is:

https://github.com/SWI-Prolog/swipl-devel/blob/master/src/pl-list.c

At line 543:

static PRED_IMPL("sort", 2, sort, PL_FA_ISO) { PRED_LD return pl_nat_sort(A1, A2, TRUE, SORT_ASC, 0, NULL, FALSE PASS_LD); }

pl_nat_sort is in the same file

The comment is historically interesting:

Natural merge sort. Code contributed by Richard O'Keefe and integrated into SWI-Prolog by Jan Wielemaker. The nice point about this code is that it uses no extra space and is pretty stable in performance. Richards claim it that many qsort() implementations in libc are very slow. This isn't the case for glibc 2.2, where this performs about the same as the previous qsort() based implementation.

Presumably Richard O'Keefe notes:

I've been using a variant of this code in a sorting utility since about 1988. It leaves the UNIX sort(1) program in the dust. As you may know, sort(1) breaks the input into blocks that fit in memory, sorts the blocks using qsort(), and writes the blocks out to disc, then merges the blocks. For files that fit into memory, the variant of this code runs about twice as fast as sort(1). Part of that is better I/O, but part is just plain not using qsort().

Dayum. That brings back memories of writing sorting algorithms in '89.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

If you just are seaching for any sorting algorithm you can always use bubblesort *cough*. It is one of the most simple and inefficient ways to sort a list, but - depending on the implementation - will run through an already sorted list in linear time. Bubblesort does not remove duplicates. This implementation does descending order:

bubblesort(List, SortedList) :- bubbleit(List, List1), ! , bubblesort(List1, SortedList) . bubblesort(List, List). bubbleit([X,Y|Rest], [Y,X|Rest]) :- X < Y, ! . bubbleit([Z|Rest], [Z|Rest1]) :- bubbleit(Rest, Rest1). ?- bubblesort([1,2,5,4,7,3,2,4,1,5,3],L). L = [7, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1].

If you want to sort for the second element in a list [_,E|] change the the first bubbleit rule to

bubbleit([X,Y|Rest], [Y,X|Rest]) :- X = [_,XX|_], Y = [_,YY|_], XX < YY, ! . ?- bubblesort([[a,3],[b,5],[c,1],[d,4]],L). L = [[b, 5], [d, 4], [a, 3], [c, 1]].
Improve this answer

3 Comments

Thank you! How would it work if you had a list of lists so [[ , ], [ , ]] and wanted to sort by the second element of each sublist?
@fewfrg i added a method to the answer
@fewfrg ^^ you can accept an answer by clicking the grey checkmark left to the answer below the upvote/donvote buttons
0

Try searching quicksort.

Here is one link: https://www.codepoc.io/blog/prolog/4934/prolog-program-to-sort-a-list-using-quick-sort

Here is another example:-

quicksort([], []). quicksort([X | Tail], Sorted):- split(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), concatenate(SortedSmall, [X| SortedBig], Sorted). split(X, [], [], []). split(X, [Y| Tail], [Y | Small], Big):- X > Y, !, split(X, Tail, Small, Big). split(X, [Y| Tail], Small, [Y | Big]):- split(X, Tail, Small, Big). concatenate([],List,List). concatenate([Item|List1],List2,[Item|List3]) :- concatenate(List1,List2,List3). ?-quicksort([1,7,4,3,6,5,9,8,12,1],L). L = [1, 1, 3, 4, 5, 6, 7, 8, 9, 12] false
Improve this answer

1 Comment

Is there a simpler way to do it? What I would like to do is sort by the second element in decending order without removing dublicates. I have at the moment done it like "sort4(List, Sorted) :- sort(2, @>=, List, Sorted)." however i am not allowed to use anything else then sort/2 so I am thought I could change the original function and implement that as a helper function.
0

The merge sort algorithm is a natural fit for Prolog. Not to mention trivial to implement in a language with recursion and lists as fundamental.

Here's a SWI Playground: https://swish.swi-prolog.org/p/swi-prolog-merge-sort.pl

merge_sort( [], [] ). % The empty list is by definition ordered merge_sort( [X], [X] ). % So is a list of length one merge_sort( Unsorted, Sorted ) :- % otherwise... partition( Unsorted, L, R ) , % partition the list into 2 halves merge_sort(L,L1), % recursively sort the left half merge_sort(R,R1), % recursively sort the right half merge(L1,R1,Sorted) % merge the newly-sorted halves . % See? simple! partition( [] , [] , [] ). % the empty list gets partitioned into two empty lists partition( [X] , [X] , [] ). % a left of length 1 gets partitioned into itself and an empty list partition( [X,Y|L] , [X|Xs] , [Y|Ys] ) :- % list of length 2 or more gets popped and divided between left and right halves partition(L,Xs,Ys) % with the remainder being recursively partitioned. . % Easy! merge( [] , [] , [] ). % merging to empty lists is trivial merge( [] , [Y|Ys] , [Y|Ys] ). % merging an empty list and a non-empty list is easy merge( [X|Xs] , [] , [X|Xs] ). % merging a non-empty list and an empty list is easy merge( [X|Xs] , [Y|Ys] , [Lo,Hi|Zs] ) :- % otherwise... compare(X,Y,Lo,Hi), % compare the two terms, put them in collating sequence merge(Xs,Ys,Zs) % and recursively merge the tails . % Easy! compare( X , Y , X, Y ) :- X @=< Y. % if X <= Y, X is Lo, and Y is Hi compare( X , Y , Y, X ) :- X @> Y. % if X > Y, Y is Lo, and X is Hi
Improve this answer

Comments