-1

I need to obtain an non-increasing order from a given random ordered elements.After working a lot, I realized that both the following codes produce different outputs. Why the codes produce different outputs?

bool cmp(int i,int j)
{
    if(i<j)
        return 0;
    return 1;
}
bool cmp(int i,int j)
{
   return i>j;
}
tharun
  • 39
  • 4
  • @pranitkothari No they are different. Although they may end up producing similar results in sorting. – Mohit Jain Dec 11 '14 at 05:06
  • I was working on a SPOJ problem. I used the first code and my program was not accepted. I used the second code and my program was accepted. – tharun Dec 11 '14 at 05:06
  • I worked on many test cases and both the codes produced same outputs.Could someone provide me better test cases? – tharun Dec 11 '14 at 05:07
  • @tharun here's your program with different output: http://ideone.com/MDwgGy – PeterT Dec 11 '14 at 09:30

3 Answers3

2

First function should be

bool cmp(int i,int j)
{
    if(i>j)
        return 1;
    return 0;
}

to get equivalent outputs.

Or alternatively use the following function:

bool cmp(int i,int j)
{
    return -1 * i < -1 * j;
}
Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
  • Could you provide me with a test case where both of my codes produce different outputs? – tharun Dec 11 '14 at 05:09
  • 1
    Yes, when both are equal. – Mohit Jain Dec 11 '14 at 05:10
  • Could you provide me with a test case where both of MY codes produce different outputs? – tharun Dec 11 '14 at 05:16
  • There may be multiple possibilities to mess up. So not without looking at the rest of the code. – Mohit Jain Dec 11 '14 at 05:18
  • @tharun you should not get a difference in normal (unstable) sorting, but in stable sorting (i.e., where the order of equivalent elements matter) – vsoftco Dec 11 '14 at 05:22
  • 2
    @MohitJain - Assuming the OP means `std::sort`, your answer doesn't seem correct in terms of what `std::sort` requires. The `>=` is not a strict-weak-ordering, which std::sort uses. For example, Visual Studio checks for things like this, and I believe your code will cause an assertion in debug builds. – PaulMcKenzie Dec 11 '14 at 05:22
  • But if I use these codes in the same program, one leads to wrong answer and other leads to accepted answer.Why? – tharun Dec 11 '14 at 05:25
  • @PaulMcKenzie Can you give me a pair where strict-weak-ordering fails? – Mohit Jain Dec 11 '14 at 05:26
  • @tharun - Are you using std::sort? If so, then the reason is what I stated in my comment. – PaulMcKenzie Dec 11 '14 at 05:26
  • PaulMcKenzie good point, @tharun related: http://stackoverflow.com/q/18291620/3093378 – vsoftco Dec 11 '14 at 05:26
  • @MohitJain - It is not correct in terms of strict-weak-ordering. If I give your compare function two values, and you return `true` that the first comes before the second value, then I call your compare function again, but switch the values on you. You again return `true`. Guess what? You lose. How can I give you a,b and you return `true` and at the same time, give you b,a and you still return true? That is the exact test that Visual Studio does to ensure the strict-weak-order is maintained. – PaulMcKenzie Dec 11 '14 at 05:29
  • @MohitJain - Correct, but the thing that messes your answer up is that dreaded `>=`. That operator has been the downfall of many a C++ programmer implementing a compare function for std::sort. You can also add `<=` to this list. Stick with `<` or `>` when implementing the compare function. – PaulMcKenzie Dec 11 '14 at 05:32
  • Could you provide me with the related references (or) is it fine if I refer to earlier strict weak ordering link? – tharun Dec 11 '14 at 05:38
  • @tharun - the link provided by `vsoftco` is ok. – PaulMcKenzie Dec 11 '14 at 05:40
  • @MohitJain - Please update your answer with the correct strict weak ordering. It sill uses `<=`, which will throw off the sort. See the link that `vsoftco` provided to understand this. – PaulMcKenzie Dec 11 '14 at 05:43
2

First things first:

Your two functions produce different results when they have the same input. So cmp(1,1) produces different results.

Undefined behavior:

Given this cmp() function:

bool cmp(int i,int j) {
    if(i<j)
        return 0;
    return 1;
}

The following statement will produce undefined behavior:

std::vector<int> x;
std::sort(x.begin(), x.end(), cmp);

The comparator passed to std::sort is required to implement Compare. One of the requirements is that cmp(1,1) will return false. Your code returns true.

Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
2

Your first function is equivalent to "not less than" i.e. "greater or equal" when what you want is "greater". Also, given that this is C++11, why not just do:

std::sort(v.begin(), v.end(), std::greater<int>());
Charlie
  • 1,487
  • 10
  • 9
  • Ahh... right... late night commenting and for some reason I saw "since c++14" in the docs and missed the line before saying "until c++14". Updated. – Charlie Dec 11 '14 at 23:51