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, Oct 03 '17 at 04: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, Oct 03 '17 at 04: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, Oct 03 '17 at 04:59

score 4 · Answer 1 · answered Oct 03 '17 at 08:03

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 03 '17 at 08:03

Jarod42

203,559
14
181
302

thanks for the answer, but, can you please explain what is proj?its' not an object,neither a function. – Saurabh Oct 03 '17 at 13:38
`proj` is a [lambda](https://stackoverflow.com/questions/7627098/what-is-a-lambda-expression-in-c11). – Jarod42 Oct 03 '17 at 14:31

score 1 · Accepted Answer · answered Oct 03 '17 at 05:03

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 03 '17 at 05:03

Gaurav Sehgal

7,422
2
18
34

Or simply `return ((a%m < b%m) || (a/m < b/m));` – CinCout Oct 03 '17 at 05:29
1

@CinCout That will not work.If `a%m > b%m` we want to return `false` and not check (`a/m < b/m)` – Gaurav Sehgal Oct 03 '17 at 05:40
Then `return ((a%m < b%m) || ((a%m == b%m) && (a/m < b/m)));` – CinCout Oct 03 '17 at 06:46
1

That assumes global `m`. – Jarod42 Oct 03 '17 at 08:04
1

@CinCout Now you've just refactored the function into a single, less readable IMO expression. – Sebastian Redl Oct 03 '17 at 08:22
@SebastianRedl It is a matter of preference, my version is easily readable to me. – CinCout Oct 03 '17 at 08:28

score -1 · Answer 3 · edited Oct 03 '17 at 08:16

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.

Custom comparator for achieving sort with multiple sort keys

3 Answers3