rtanmay's blog

Doubt about comparison function in sorting array of structures.
By rtanmay, history, 6 years ago, In English

Hello,

I was solving this problem. In this I have sorted the array of structures. 

//This is my structure:
typedef struct node
{
	int a,b,c;
} node;

Submission

//This gets runtime error on test-32.
//Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).
bool compare(node n1, node n2)
{
	if(n1.c > n2.c) return false;
	else return true;
}

Submission

//However this gets accepted, only change is in >=
bool compare(node n1, node n2)
{
	if(n1.c >= n2.c) return false;
	else return true;
}

Why is this error coming? I thought even if we give only > then for equal value it will return true, so there should not be any problem between comparison of equal elements.

Thank you

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

because if x = y then both x < y and y < x according to your first submission. It causes UB while sorting.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I am sorry, but can you explain where both x<y and y<x are happening? In the compare function if x==y, then it returns true (meaning that x will come before y) but since they are same then it does not matter.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And also x = y means that y comes before x . It should return false if x = y.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Your function says that a < a for any a. Such a function can't be a comparator

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you, I understand where I was making mistake.

        → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The comparator function in stl::sort() follows and requires strict weak ordering.

eg. Consider Comp for ascending order: 

bool comp(int x, int y){   
    if(x < y) return true;  // this will ensure that x comes before y if and only if(x < y).
    return false;
}

And This is what you are doing :

bool comp(int x, int y){   
    if(x > y) return false;  // this function will return true even when (x == y) which does not follow
    return true;             // strict weak ordering.
}

Your accepted solution solves this problem and that is why it is not throwing any error.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! I didn't knew about strict weak ordering.

    → Reply