1

How are the binary predicates evaluated?

For example, if I want to sort in the descending order, then should I write:

bool isGreater(int x, int y) 
{
    return x > y;
}

or

bool isGreater(int x, int y) 
{
    return y > x;
}

What exactly is the difference between the two? I understand that the two parameters would be compared to each other, but what should the return result be - true or false? And how does it matter? So, my question basically is, how do I determine if the first argument should go before the second one, if I don't know the order in which they will be passed?

The sort() function would be called in this fashion (height is the array to be sorted):

sort(height, height+N, isGreater);

Note: I did refer links like this one and this one, but they don't explicitly focus on this problem.

Could someone please clarify my doubt? Thanks!

Community
  • 1
  • 1
  • Yes, it is. But how do I conclude which one to use, when I want to sort in the descending order? How would the binary predicate be called and what would its parameters be? –  Nov 27 '16 at 22:27
  • 1
    The predicate should return true if the first argument should go before the second argument. So for descending order you want x > y. – tukra Nov 27 '16 at 22:30
  • @tukra, Could you please elaborate? Suppose the predicate is called first for the values 1 and 3. So the predicate would return `false` since `1<3`. Next, it is called for, say, 1 and 5. It would again return `false` since '1<5'. Now, what about the relative ordering of 3 and 5? Will it be called again for 3 and 5? –  Nov 27 '16 at 22:36
  • 1
    Yes of course. The algorithm will perform as many comparisons as needed to determine the relative order of all elements. – Igor Tandetnik Nov 27 '16 at 22:40
  • 1
    The predicate will be called any time the sort algorithm needs to decide how any two elements will be ordered relative only to themselves. We are ignorant as to how the sorting algorithm works. The predicate could potentially be called to compare any two elements in our collection. It will typically be called many many times in the course of a single sort operation. – tukra Nov 27 '16 at 22:45
  • @tukra, okay. So do you suggest a custom descending sorting implementation would be preferable to this one? –  Nov 27 '16 at 22:49
  • 1
    No, the whole point of using predicates is that you only need one sorting algorithm. Enjoy the fact that it's easy. – tukra Nov 27 '16 at 22:55
  • @tukra, you say, *if the first argument should go before the second argument*; how do I know if the first element should go first or second, since I don't know how they are called? –  Nov 30 '16 at 22:11

1 Answers1

2

Here is a very simple ascending order sorting algorithm in psuedo code:

for i ← 1 to length(A)-1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

Same thing with a predicate "MyCompare(x, y) { return x <= y; }" looks like this:

for i ← 1 to length(A)-1
    j ← i
    while j > 0 and MyCompare(A[j-1], A[j]) == false
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

Now the sort algorithm can sort in any order just by changing the predicate. Since this predicate is an argument to std::sort that means std::sort can sort in any order.

tukra
  • 921
  • 8
  • 13
  • Thanks for you answer. However, my question is not specifically about sorting in the ascending order. I have rephrased my question and stated it precisely in bold. –  Nov 30 '16 at 22:30
  • The job of the predicate is ONLY to determine the proper order of the two arguments. If you want to sort in descending order then your predicate will be: bool MyCompare(x,y) { return x > y; }. If x = 3 and y = 5 it returns false to indicate that y should come before x. If x = 5 and y = 3 it will return true to indicate that x should come before y. Examine how this works in the given sort example. You can see that the sort will reorder values when it gets false from the predicate. But the details of how the sort works are ultimately inconsequential. Your predicate simply needs to be correct. – tukra Nov 30 '16 at 23:12
  • So, if I write `bool MyCompare(x,y) { return x < y; }`, won't this work as well? If `x = 3` and `y = 5`, then it will return true; else false. Why doesn't this work to give me the descending order? Sorry for so many questions, I appreciate your help. –  Nov 30 '16 at 23:16
  • That will sort in ascending order. return x < y for ascending. return x > y for descending. I'm not able to understand why you are confused. These are the opposite of each other so they give opposite results as we would logically expect. – tukra Nov 30 '16 at 23:23
  • When you get `x = 3` and `y = 5` and you return `true` that `true` is letting the sort alg know that 3 should come before 5 which is ascending order. – tukra Nov 30 '16 at 23:29
  • I got you! Thank you!! I appreciate your help. –  Nov 30 '16 at 23:29