How can I sort a pair of vector in some given range?

Question

I know how to sort pair of vectors using std:sort(v.begin(), v.end()); But this will sort all the pairs of the vector. But I want to sort the vector in a specified range.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool sortbysecdesc(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}


int main(){
    int n;
    cin>>n;
    
    ll a[n];
    ll b[n];
    
    vector<pair<ll, ll>> v;
    vector<pair<ll, ll>>::iterator itr;

    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    for (int i = 0; i < n; i++) {
        cin>>b[i];
    }
    
    for (int i = 0; i < n; i++) {
        v.push_back(make_pair(a[i],b[i]));
    }
    
    //sorting the pair in descending order with second element
    sort(v.begin(), v.end(), sortbysecdesc);
    
 
    for (itr=v.begin(); itr!=v.end(); itr++) {
        
        /* Logic to be implement */
        
    }
    return 0;
}

Code explanation- Here I'm taking input 2 arrays and making a pair of vector by combining first_array[i] element with second_element[i] element. Such as - first_array = {1, 5, 4, 9} and second_array = {2, 10, 5, 7} then the vector of pair's will be of size = 2*size_of(first/second array) and elements will be [{1, 2}, {5, 10}, {4, 5}, {9, 7}]. Then I'm sorting these pair in descending order according to second elements of pairs i.e, all elements of second array.

Now I wanna sort the vector form where second elements are equal.

eg - if the vector is [{1,6} , {4,5}, {3,5}, {8,5}, {1,1}]. Here 5 occurs three time in second element of pair so sort their first index in ascending order. Expected result - [{1,6} , {3,5}, {4,5}, {8,5}, {1,1}]

Note - We had already sorted the second element in descending order.

Your code have some of the *bad* habits commonly show-cased on so-called "competition" or "online judge" sites. Please don't use such sites to learn anything, that's not what they're for (unless you want to know how bad and often invalid code look like, as is the case with your program (both the bad habits and being invalid C++)). — Some programmer dude, Oct 25 '21 at 13:21
Have you considered simply adding `if(a.second == b.second) { return a.first < a.second; }` section to your comparator, `sortbysecdesc()`? — , Oct 25 '21 at 13:21
@Frank hey that works fine :) but if wanna compare if second element of the final vector occurs more than once :( — Uttam, Oct 25 '21 at 13:24
@Uttam, that's what `if(a.first == a.second)` does. it detects when the second element happens more than once. — , Oct 25 '21 at 13:25
Btw, if you could invert the order of elements in your pairs (that is, pair instead of ), the vector would sort automatically in just the way you want it to: https://stackoverflow.com/a/2819287/10908201 — DL33, Oct 25 '21 at 13:27
@DL33 this looks somewhat I'm looking for :) Can you please post this in answer section after modifying my entire code — Uttam, Oct 25 '21 at 13:28

Vlad from Moscow · Accepted Answer · 2021-10-25T13:49:22.673

4

What you need is something like the following

#include <tuple>
#include <vector>
#include <iterator>
#include <algorithm>

//...

std::sort( std::begin( v ), std::end( v ),
           []( const auto &p1, const auto &p2 )
           {
               return std::tie( p2.second, p1.first ) < std::tie( p1.second, p2.first );
           } );

Here is a demonstration program.

#include <iostream>
#include <tuple>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<std::pair<long long, long long>> v =
    {
        {1,6} , {4,5}, {3,5}, {8,5}, {1,1}
    };
    
    std::sort( std::begin( v ), std::end( v ),
               []( const auto &p1, const auto &p2 )
               {
                    return std::tie( p2.second, p1.first ) <
                           std::tie( p1.second, p2.first );
               } );
               
    for ( const auto &p : v )
    {
        std::cout << "{ " << p.first << ", " << p.second << " } ";
    }
    
    std::cout << '\n';
    
               
    return 0;
}

The program output is

{ 1, 6 } { 3, 5 } { 4, 5 } { 8, 5 } { 1, 1 }

edited Oct 25 '21 at 13:49

answered Oct 25 '21 at 13:32

Vlad from Moscow

301,070
26
186
335

3

As OP mixes descending and ascending order, we have to mix parameters too: `return std::tie(p2.second, p1.first) < std::tie(p1.second, p2.first);`. – Jarod42 Oct 25 '21 at 13:41
I tried your approach too. But :( Can you please head to this practice question https://www.codechef.com/UAPRAC/problems/PSORT3 – Uttam Oct 25 '21 at 13:43
@Jarod42 Thanks. I have updated the code. – Vlad from Moscow Oct 25 '21 at 13:49
@VladfromMoscow hey thankyou so much for your help :) but why are you using `const` everywhere and what does std:tie() do. Can you please explain – Uttam Oct 25 '21 at 15:01
Then I will mark this ans the accepted ans :) But for now I am doing upvote – Uttam Oct 25 '21 at 15:02

Sumit Jha · Answer 2 · 2021-10-25T17:36:22.133

3

You have to update your sorting function. Try this.

bool sortbysecdesc(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second == b.second ? a.first < b.first : a.second > b.second;
}

Demo

edited Oct 25 '21 at 17:36

answered Oct 25 '21 at 13:23

Sumit Jha

1,601
11
18

bro but my `sortbysecdesc` function works fine. I want to check the final vector of pairs and if 2nd element of a vector occurs more than one then I wanna sort that much of first element of vector in ascending order – Uttam Oct 25 '21 at 13:26
1

@Uttam: Have you tried proposed answer? – Jarod42 Oct 25 '21 at 13:27
@SumitJha: function name should be changed though (or lambda used to avoid name completely ;-) ). – Jarod42 Oct 25 '21 at 13:29
@Jarod42 yup but it didn't worked or maybe I'm doing anything wrong can you please post the entire code as I asked in question. – Uttam Oct 25 '21 at 13:31
@Uttam: If **you** provided MCVE, you just have to replace your function by this one. [Demo](http://coliru.stacked-crooked.com/a/976e55c0908f74a8) added anyway. – Jarod42 Oct 25 '21 at 13:39
@Jarod42 yep I tried that but it gave wrong ans. See this practice question https://www.codechef.com/UAPRAC/problems/PSORT3 – Uttam Oct 25 '21 at 13:42
1

@Jarod42 Thanks for adding the demo. – Sumit Jha Oct 25 '21 at 13:45
@Uttam Could you give an example that is not working by simply replacing your `sortbysecdesc`with this one. – Sumit Jha Oct 25 '21 at 13:50
@Uttam: Issue might come from the way you output result too (extra space at the end for example). – Jarod42 Oct 25 '21 at 13:51
@Sumit i'm alao not getting why the code is not passing all the test case – Uttam Oct 25 '21 at 13:54
@Uttam I think the problem is how you collect data into vector using cin. https://godbolt.org/z/G7hc6nxMT . I have updated the demo with comments. Have a look. – Sumit Jha Oct 25 '21 at 17:27

How can I sort a pair of vector in some given range?

2 Answers2