CODEWITHSUNDEEP
c++
kranti sairam
kranti sairam

Reputation: 526

How does below comparator function works in c++?

bool comp(int a,int b){

    if ((a > 0 && b > 0) || (a < 0 && b < 0))
        return false;

    if ((a > 0) && (b < 0))
        return false;
}

To a given array, which contains positive and negative integers, the above function is useful to rearrange the array such that, negative integers followed by positive integers and it preserves the order of elements.

Example: 

int arr [] = {1,2,-3,-1}, n=sizeof(arr)/sizeof(int);

sort(arr,arr+n, comp);

output : {-3,-1,1,2}

But I am unable to understand how it is working, Could someone explain ?

Upvotes: 0

Views: 117

Answers (2)

Victor Istomin
Victor Istomin

Reputation: 1156

But I am unable to understand how it is working, Could someone explain ?

I try to explain how it's supposed to work, but actually, it does not work :)

bool comp(int a, int b) {

    if((a > 0 && b > 0) || (a < 0 && b < 0))
        return false;

    if((a > 0) && (b < 0))
        return false;

    return true;
}

This code tries to compare signs: checking whether sign of a is "less" than sign of b. Assuming that negative is "less" than positive. So, sign of -1 is less than sign of 1, and sign of -3 is not less than sign of -1.

The problem here is that comparator should always conform with https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.

In short, strict weak ordering is: for any a and b, only one condition is true: a < b, or b < a, or b == a. There should be no case when more of one condition is true.

When strict weak ordering is violated in production code, very bad things will happen: overtimes, failed deadlines, and even worse.

Your sort() will fail on this array: { 1, 0, 2, 0, -3, 0,-1 } because strict weak ordering is violated: both comp(-1, 0) is true and comp(0, -1) is true.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234685

Your assertions are incorrect on two counts:

  1. std::sort is not guaranteed to preserve the order of elements that don't need sorting, if you get my meaning.

  2. The behaviour of your comp function is undefined as it doesn't have an explicit return value on all control paths.

One remedy is to use std::stable_sort which will preserve the order of elements as best it can. The comparator function can be adjusted such that it's true if the first argument is negative and the second is positive (let's define 0 to be positive):

bool comp(int a, int b){
    return a < 0 && b >= 0;
}

Another remedy is to use std::stable_partition.

Upvotes: 7

Related Questions