CODEWITHSUNDEEP
c++sortingc++14
Sujeet Sawala
Sujeet Sawala

Reputation: 1

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

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

Upvotes: 0

Views: 91

Answers (2)

xryl669
xryl669

Reputation: 3614

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.

Upvotes: 1

lubgr
lubgr

Reputation: 38295

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.

Upvotes: 4

Related Questions