0

I would like to sort a list of tuple in descending order, based on the second value of the list, without using built-in sort predicate.

Example: (Name, Age).

unsorted_list = [(mary, 20), (jack, 50), (bob, 16), (bill, 20) ].

sorted_list = [(jack, 50), (bill, 20), (mary, 20), (bob, 16)].

Does anyone know an elegant way to do this?

2
  • 1
    (1) Lookup a written out, simple Prolog sort predicate implementation that operates on a simple list of numbers. They're all over the place, so i'm sure you can find one. (2) Modify it to use (Name, Number) instead of just Number. That is, any place you see the use of a number in such a predicate, except when it is doing a comparison, use (Name, Number). In the comparison, though, just use the number. If you do a little digging and thinking, this should get you on your way.
    – lurker
    Dec 14, 2017 at 11:57
  • related: see my answer here
    – CapelliC
    Dec 14, 2017 at 11:59

2 Answers 2

6

There are many ways to implement this. One way would be to implement your customized pair-sort from scratch, the advantage of this would be that you know exactly the implementation of your algorithm and thus the complexity, but this may not be so elegant.

Another more elegant way would be to use Prolog's ISO predicate keysort/2, which sorts a list of pairs of the form [X1-Y1, X2-Y2, ...] and the sort is based on first argument of pair (Xi). So you need to change your list in form [-20-mary, -50-jack, -16-bob, -20-bill] and then apply keysort/2. Note that thanks to @false's comment in order to achieve a stable solution for descending order we could negate the numbers and sort iin ascending order the negated numbers:

:-use_module(library(clpfd)).

swap_internals((X,Y), Y1-X):- Y1 #= -Y.

pair_sort(L,Sorted):- 
      maplist(swap_internals, L, L2),
      keysort(L2, L3),
      maplist(swap_internals, Sorted, L3).

In the above you build the list in the appropriate form using maplist/3 and swap_internals/2, sort it with keysort/2, and change it back using again maplist/3.

Example:

   ?- pair_sort([(mary, 20), (jack, 50), (bob, 16), (bill, 20) ],L).
    L = [(jack, 50),  (bill, 20),  (mary, 20),  (bob, 16)].


The is another way for descending order, just use sort/4 predicate:

sort(2, @>=, L, Sorted).

Example:

?- sort(2,@>=, [(mary, 20), (jack, 50), (bob, 16), (bill, 20) ], L).
L = [(jack, 50),  (mary, 20),  (bill, 20),  (bob, 16)].

This way is obvious more easy though it is not an ISO predicate.



EDIT

I didn't see the "without using built-in sort predicate" part of the question, so you could just write a typical merge sort changing the 3rd rule of merge/2 below in order to handle pairs:

halve([], [], []).
halve([A], [A], []).
halve([A,B|Cs], [A|X], [B|Y]) :- halve(Cs, X, Y).

merge([], Ys, Ys).
merge(Xs, [], Xs).
merge([(X1,X2)|Xs], [(Y1,Y2)|Ys], M) :-
   (  
      X2 > Y2 -> M = [(X1,X2)|Ms], merge(Xs, [(Y1,Y2)|Ys], Ms) 
    ; M = [(Y1,Y2)|Ms], merge([(X1,X2)|Xs], Ys, Ms) 
   ).

mergeSort([], []).
mergeSort([E], [E]).
mergeSort([E1,E2|Es], SL) :- 
     halve([E1,E2|Es], L1, L2),
     mergeSort(L1, SL1),
     mergeSort(L2, SL2),
     merge(SL1, SL2, SL). 

Example:

?- mergeSort([(mary, 20), (jack, 50), (bob, 16), (bill, 20) ],L).
L = [(jack, 50),  (bill, 20),  (mary, 20),  (bob, 16)] ;
false.
6
  • (Warning: direct reversal questions stability!)
    – false
    Dec 14, 2017 at 11:12
  • 1
    keysort/2 is stable. That is, two items with identical key will remain in the same original order. By reversing, they are reversed which is certainly not what a descending order expects.
    – false
    Dec 14, 2017 at 11:14
  • @false, thanks !!! I really didn't see it in the first place but you're right!! I just kept answer with sort/4.
    – coder
    Dec 14, 2017 at 11:18
  • And why don't you negate the number??
    – false
    Dec 14, 2017 at 11:43
  • 1
    Yep, that's the work I told the OP in my comment to their post that they needed do to solve their problem. :)
    – lurker
    Dec 14, 2017 at 14:19
1

Although non built-in implementation was requested in original post, I would still like to add to the comment posted by @coder that there are few additional sorting predicates available if you are using Swi-Prolog: predsort/3 and sort/4

predsort/3 is of particular interest, as it allows you to specify custom sort predicate:

compare_tuples_descending('<', (_, X), (_, Y)) :- X > Y, !.
compare_tuples_descending('>', _, _).

sort_tuples_descending(Unsorted, Sorted) :-
    predsort(compare_tuples_descending, Unsorted, Sorted).

Usage example:

?- sort_tuples_descending([(mary, 20), (jack, 50), (bob, 16), (bill, 20)], S).
S = [(jack, 50), (bill, 20), (mary, 20), (bob, 16)].

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.