How to sort a vector of pairs in descending order and by the second element?

Question

I am working on a programming challenge and I have already looked at this topics before asking:

Sorting elements of vector where each element is a pair [duplicate]

How do I sort a vector of pairs based on the second element of the pair?

And the situation is like this:

-I have my vector of pairs: vector< pair<int, int> > rank;

-And I have already implemented a predicate to compare and sort the vector of pairs by the second element and in descending order:

struct predicate
{
    bool operator()(const std::pair<int, int> &left, const std::pair<int, int> &right) 
    {
         return left.second < right.second;
    }
}

sort(rank.rbegin(), rank.rend(), predicate());

The programming challenge will give repeated values for the second element, and for that cases, I must leave the first element ordered by the time it was inserted to the vector of pairs, for example:

K V
1 3
2 4
4 5
33 3

Sorted must be:

4 5
2 4
1 3
33 3

The problem comes when I test my solution with a test case I designed:

K V
1 2
16 3
11 2
20 3
18 2
39 39
23 22
12 19
123 4
145 6
3 5
26 4
9574 4
7 1
135 5
193 99
18237 3
22 4
1293 3
3471 33

It's supposed the output should be like this, after sorting the vector:

193 99
39 39
3471 33
23 22
12 19
145 6
3 5
135 5
123 4
26 4
9574 4
22 4
16 3
20 3
18237 3
1293 3
1 2
11 2
18 2
7 1

But instead of that, I got some elements ordered by the first value too:

193 99
39 39
3471 33
23 22
12 19
145 6
3 5
135 5
123 4
26 4
9574 4
22 4
20 3 ->Changed element
16 3 ->Changed element
18237 3
1293 3
18 2 ->Changed element
11 2
1 2 ->Changed element
7 1

Why is happening this?? What am I doing wrong?? Help will be appreciated

Answer 1

It's Called stable_sort that means if 2nd value is same then it will follow same sorting as input like 16 3 is before 20 3 in input. so in result 16 3 will be before 20 3 . in c++ code you should be add stable_sort() instead of sort(). Here is my accepted code :

#include <bits/stdc++.h>
using namespace std;
bool compare( const pair<long long int,long long int>& x, const pair<long long int, long long int>& y )
{

    return (x.second>y.second);

}
int main()
{
    vector<pair<long long int,long long int> >a;
    long long int n,i,j,b,c;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>b>>c;
        a.push_back(pair<long long int,long long int>(b,c));
    }
    stable_sort(a.begin(),a.end(),compare); //must include stable_sort
    vector<pair<long long int,long long int> >::iterator p;
    for(p=a.begin();p!=a.end();p++)
    {
        cout<<p->first<<" "<<p->second<<endl;
    }
    return 0;



}

Answer 2

Try the following code

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

int main()
{
    std::vector<std::pair<int, int>> v;

    // If your compiler does not support list initialization then you can use push_back
    v.push_back( std::pair<int, int>( 1, 3 ) );
    v.push_back( std::pair<int, int>( 2, 4 ) );
    v.push_back( std::pair<int, int>( 4, 5 ) );
    v.push_back( std::pair<int, int>( 33, 3 ) );

    // The lambda expression can be substituted for a function with the same body
    std::sort( v.begin(), v.end(),
               []( const std::pair<int, int> &p1, const std::pair<int, int> &p2 )
               {
                   return ( p1.second > p2.second || 
                          ( !( p2.second > p1.second ) && p1.first < p2.first ) );
               } );

    for ( const auto &p : v ) std::cout << p.first << '\t' << p.second << std::endl;
    std::cout << std::endl;
}

The output is

4       5
2       4
1       3
33      3

Your predicate will look the following way

struct predicate
{
    bool operator ()( const std::pair<int, int> &left, const std::pair<int, int> &right ) const
    {
        return ( left.second > right.second || 
               ( !( right.second > left.second ) && left.first < right.first ) );
    }
};

Answer 3

std::sort does not guarantee that the order of "equal" elements remains unchanged. For that you want std::stable_sort. "Equal" in this context means two elements a and b for which

!((a < b) || (b < a))