Compare function doubt!

1 
bool cmp(const pii a,const pii b){
     if(a.S*b.F+b.S>a.F*b.S+a.S)return true;
     else return false;
}

Can anyone explain with examples, how this sort function will work?
Say
2 2
3 1
4 3

2

There isn’t a sort function in your post; just a compare function. The precise workings of a sort function depend on the underlying algorithm :slight_smile:

If you mean “what order will they end up in”, it depends on what pii, pii::F and pii::S are - are they std::pair<int, int>, std::pair<int, int>::first and std::pair<int, int>::second, respectively?

1 Like
3

They are std::pair<int, int>

1 Like
4

Your example:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Ugh.
#define pii std::pair<int, int>
#define F first
#define S second

bool cmp(const pii a,const pii b){
    cout << "comparing: a = {" << a.first << "," << a.second << "} and b = {" << b.first << "," << b.second << "}" << endl;
    cout << "a.second * b.first + b.second: " << (a.S*b.F+b.S) << endl; 
    cout << "a.first * b.second + a.second: " << (a.F*b.S+a.S) << endl;
    if(a.S*b.F+b.S>a.F*b.S+a.S)
    {
        cout << "a < b" << endl;
        return true;
    }
    else 
    {
        cout << "a >= b" << endl;
        return false;
    }
}

int main()
{
    vector<pii> toSort = { 
        {2, 2},
        {3, 1},
        {4, 3}
    };

    sort(toSort.begin(), toSort.end(), cmp);

    cout << "Sorted: " << endl;
    for (const auto& [first, second] : toSort)
    {
        cout << " {" << first << ", " << second << "}" << endl;
    }
}

gives:

a.second * b.first + b.second: 4
a.first * b.second + a.second: 7
a >= b
comparing: a = {3,1} and b = {2,2}
a.second * b.first + b.second: 4
a.first * b.second + a.second: 7
a >= b
comparing: a = {4,3} and b = {2,2}
a.second * b.first + b.second: 8
a.first * b.second + a.second: 11
a >= b
comparing: a = {4,3} and b = {3,1}
a.second * b.first + b.second: 10
a.first * b.second + a.second: 7
a < b
comparing: a = {4,3} and b = {2,2}
a.second * b.first + b.second: 8
a.first * b.second + a.second: 11
a >= b
Sorted: 
 {2, 2}
 {4, 3}
 {3, 1}
2 Likes
5

How is this sorting, I still am not understanding? Why it compares same set of values twice as given in output? How does this code work its way to sort the final list in form:
2 2
4 3
3 1

6

If you’re asking how std::sort works internally, then that’s a complex question (and knowing the answer is not very helpful, to be honest). Take a look at e.g. this or this.

2 Likes
7

OK. Thank you very much!:slightly_smiling_face:

1 Like