Comparator function in sort() method c++. Getting different solution for large array of numbers

Question

Unable to understand Comparator function behaviour when sorting an array of 1000 elements with value 1000000 in descending order. (The array is 1 indexed)

The first instance of definition of comparator function has random zeroes at some indexes in the array.

The second instance of definition of comparator function works fine. Could anyone explain why this is happening

bool func(long long a, long long b){
  return (a >= b);
}

sort (A+1, A + 1000 + 1, func);

bool func(long long a, long long b){
  return (a > b);
}

sort (A+1, A + 1000 + 1, func);

Output 1: 1000000 1000000 1000000 0 0 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000

Output 2: 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000

Read about compare. Your version with >= doesn't satisfy strict weak ordering requirements, it leads to UB. — rafix07
– rafix07, Commented Jul 15, 2019 at 10:55

lubgr · Accepted Answer · 2019-07-15 10:55:35Z

4

When you pass custom comparison functions to std::sort, they must induce what is called a "strict weak ordering relation" (see here). Your function

bool func(long long a, long long b){
  return (a >= b);
}

does not satisfy these requirement (e.g. func(42, 42) != false). This result in undefined behavior, the resulting sequence can by anything.

answered Jul 15, 2019 at 10:55

lubgr

38.6k3 gold badges71 silver badges119 bronze badges

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

2 Comments

Lightness Races in Orbit Over a year ago

Just to add that, more specifically, the algorithm assumes that your ordering satisfies that requirement, and will not keep checking that assumption along the way (because that would be slow) - we could probably work out which exact step of the algorithm falls foul of your error and how exactly this results in trouble, but we generally do not bother because (a) it would take time, and (b) it would not help us fix the problem.

Lightness Races in Orbit Over a year ago

The key is that, in this context, >= is not the opposite of < (possibly unintuitive at first glance!)

xryl669 · Accepted Answer · 2019-07-15 20:03:46Z

The issue you are observing is due to sorting equal values. If you have a sequence 3 3 3 3 4 and try to sort it, the algorithm using only >= (or any other equal sign) can not distinguish what order the number should be placed.

In my previous example, when it's comparing the first 3 with the second one, the compare function says the first is less than the second. Then if for whatever reason, it's trying to compare the second with the first, the same function will say that the second is less than the first. This confuses the algorithm and make it undefined behavior.

Because of this, the standard expect you provide a compare function that's not ambiguous. It's easy in your case, just use the operator without equality:

inline bool func(long long a, long long b) { return b < a; }

Please notice that if the algorithm needs to know if two value are equal, it needs to call your function twice (bool isEqual(a,b) = !func(a,b) && !func(b,a)). It's not optimal (2 tests instead of one), so that's why the spaceship operator was added in C++20.

Collectives™ on Stack Overflow

Comparator function in sort() method c++. Getting different solution for large array of numbers

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related