Блог пользователя prac64

Sort two arrays based on one, IN-PLACE [C++]
Автор prac64, история, 2 года назад, По-английски

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 ?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится

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);
→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

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?

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

→ Ответить