prac64's blog

Sort two arrays based on one, IN-PLACE [C++]
By prac64, history, 3 years ago, In English

Hello codeforces,

We all have done the classic question where there are two arrays, lets say, one denoting user-id and other denoting tenure. Now we need to sort both arrays so users with shortest tenure come first. Ex:

user-ids: [34, 51, 21, 22, 37] tenure : [ 1, 4, 1, 10, 3 ]

answer:

user-ids: [21, 34, 37, 51, 22] tenure: [ 1, 1, 3, 4, 10]

This is pretty straight forward with creating array of pairs and using library sort. However this ends up using O(n) extra memory. Surely if I wrote my own selection-sort or merge-sort, I could manage to do it in in-place by book-keeping the indexes and updating both arrays myself.

My question is, how can we do this in C++ using library sort, inplace, without creating a new array ?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

You can use lambda function like this

sort(user_ids, user_ids + user_ids_size, [&](int i, int j) {
    return tenure[i] < tenure[j];
});

or a function like this

bool cmp(int i, int j) {
    return tenure[i] < tenure[j];
}

sort(user_ids, user_ids + user_ids_size, cmp);
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your solutions only works if user_ids is a permutation of $$$0, 1, ..., n-1$$$.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

use struct

struct node{
    int id,tenure;
}a[N];
bool cmp(node a1,node b1){
    return a1.id<b1.id;
}
sort(a,a+N,cmp);

UPD: Why so much devote?

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Hello. Since no one has answered your question, I think it's my turn.

You are looking for a special type of iterator that combines the two arrays. This can be done if you know C++ well. I don't, though. Anyway, someone has written a zip iterator implementation. You can use it to sort two arrays in place.

All you need to do is copy and paste the code in the ZipIterator.hpp file. Here's the code that solves your problem.

Of course you shouldn't use it in a contest though. But I answered your question, lol.

→ Reply