How can I order an array with duplicate values?

Question

I want to order an array of stuffs that may have duplicates. For example:

int values[5] = {4, 5, 2, 5, -1};
int expected[5] = {1, 2, 0, 2, -1};

Here 2 is the smallest element so its order is 0. 4 is the 2nd smallest so its order is 1. 5 is the 3rd smallest and I want both of them have the order 2. I want to skip over certain elements (-1 in the above example) so these elements will have order -1.

How do I do this in C++ or describe an algorithm ?

Thanks

In other words you want to compute their rank in a sorted set? How would you handle another element 10 - would this be order 3, ignoring that there were two order 2s, or order 4? I suspect you're going to have to sort the subset of values that you don't want to ignore, then count into that sorted set to determine ranks into a map or similar, then walk your original set and look up each element in the rank map. But there may be better ways. — Rup
– Rup, Commented Nov 11, 2014 at 22:39
Yes, I want to compute the rank. So {10, 4, 5, 2, 5, -1} will have rank {3, 1, 2, 0, 2, -1}. But I don't want to change the order of elements in the "values" array. — cody
– cody, Commented Nov 11, 2014 at 22:47
How many elements you do not want to consider? Is there any other element other than -1 that you don't want to consider? — Edwin
– Edwin, Commented Nov 11, 2014 at 22:47

Niklas B. · Accepted Answer · 2014-11-11 23:00:03Z

1

Just sort the array, then assign each element its rank:

vector<int> v(values, values + 5);
v.push_back(-1);
sort(begin(v), end(v));
v.resize(unique(begin(v), end(v)) - begin(v));
for (int i = 0; i < 5; ++i)
  expected[i] = lower_bound(begin(v), end(v), values[i]) - begin(v) - 1;

This assumes that all the elements are non-negative or -1. If there are negative elements that are smaller than -1, you need to special case the -1.

answered Nov 11, 2014 at 23:00

Niklas B.

95.8k18 gold badges201 silver badges228 bronze badges

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

Collectives™ on Stack Overflow

How can I order an array with duplicate values?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related