Custom comparator for achieving sort with multiple sort keys

Question

There is an array of integers and there is a number M. The array needs to be sorted array with respect to the following criterion:

(arr[i] % M, arr[i] / M)

That is, the ordering is determined based on the result of arr[i] % M, and, in case of a tie, based on the result of arr[i] / M.

I know that a custom comparator can be passed like this:

std::sort(arr, arr + n, comp) // comp is a custom comparator.

But the answer would probably not be correct if I apply sort simply twice.

Is there any way with which we can use the std::sort() to achieve this functionality?

show input and expected output.Is it like you want the values to be sorted by arr[i]%m, and if two values are equal then you want to sort by arr[i]/M ? — Gaurav Sehgal
– Gaurav Sehgal, Commented Oct 3, 2017 at 4:51
eg:array=4,3,2,1,M=2 after first pass:array:4,2,3,1 after second pass(the final answer):array:2,4,1,3 — Saurabh
– Saurabh, Commented Oct 3, 2017 at 4:55
std::sort is not stable, you could get 2,4,1,3 after first pass.You might be interested in std::stable_sort — Gaurav Sehgal
– Gaurav Sehgal, Commented Oct 3, 2017 at 4:59

Jarod42 · Accepted Answer · 2017-10-03 08:03:34Z

4

Simply:

auto proj = [&](int e) { return std::make_tuple(e % M, e / M) };
std::sort(std::begin(arr),
          std::begin(arr) + n,
          [&](int lhs, int rhs) { return proj(lhs) < proj(rhs); });

answered Oct 3, 2017 at 8:03

Jarod42

227k15 gold badges214 silver badges350 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Saurabh Over a year ago

thanks for the answer, but, can you please explain what is proj?its' not an object,neither a function.

Jarod42 Over a year ago

proj is a lambda.

Gaurav Sehgal · Accepted Answer · 2017-10-03 05:03:50Z

1

you want the values to be sorted by arr[i]%m, and if two values are equal then you want to sort by arr[i]/m.

bool cmp(int a,int b)
{
    if(a%m < b%m)
        return true;
    if(a%m > b%m)
        return false;
    return a/m < b/m;
}

See here for a working example.

answered Oct 3, 2017 at 5:03

Gaurav Sehgal

7,4972 gold badges20 silver badges35 bronze badges

6 Comments

CinCout Over a year ago

Or simply return ((a%m < b%m) || (a/m < b/m));

Gaurav Sehgal Over a year ago

@CinCout That will not work.If a%m > b%m we want to return false and not check (a/m < b/m)

CinCout Over a year ago

Then return ((a%m < b%m) || ((a%m == b%m) && (a/m < b/m)));

Jarod42 Over a year ago

That assumes global m.

Sebastian Redl Over a year ago

@CinCout Now you've just refactored the function into a single, less readable IMO expression.

|

Jarod42 · Accepted Answer · 2017-10-03 08:16:08Z

-1

Pair arr[i]%M and arr[i]/M now calling sort(arr,arr+n) in ascending order with respect to arr[i]%M and if arr[i]%M are equal with arr[i]/M. If you want a different sorting write a function and call sort like sort(arr,arr+n,func). Also see this. http://www.cplusplus.com/reference/algorithm/sort/
http://www.cplusplus.com/reference/utility/pair/

vector<pair<int,int> > v;
for(int i = 0;i < n;i++){
    v.push_back(a[i]%m,a[i]);
}
sort(v.begin(),v.end());

Here sorting by a[i] is equivalent to sorting by a[i]/n and you can get second elements by v[i].second.

edited Oct 3, 2017 at 8:16

Jarod42

227k15 gold badges214 silver badges350 bronze badges

answered Oct 3, 2017 at 4:57

gst1502

3061 silver badge10 bronze badges

Collectives™ on Stack Overflow

Custom comparator for achieving sort with multiple sort keys

3 Answers 3

2 Comments

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related