How do I sort not the elements of an array, but it's indexes?

Question

So I have an array like this:

int array[]={2, 4, 3, 1};

I want to sort this in descending order, but get the original indexes, like this: {1, 2, 0, 3} How do I solve this so it works with an array of any size? Also, is there a solution that doesn't need C++11?

Thanks!

Can you elaborate the question? – kometen Nov 21 '17 at 12:52 — kometen, Nov 21 '17 at 12:52
It is unclear what the problem is. – Ron Nov 21 '17 at 12:55 — Ron, Nov 21 '17 at 12:55

marom · Answer 1 · 2017-11-21T12:57:24.853

5

I would go for something like this:

std::vector<std::pair<int, int>> temp ;
int idx = 0 ;
for (auto x : array)
    temp.push_back(std::make_pair(x, idx++)) ;
std::sort(temp.begin(), temp.end()) ;

You can easily get rid of the range for (the only C++11 construct used here). There is no need to define a comparison for std::pair, the default one is OK.

edited Nov 21 '17 at 12:57

answered Nov 21 '17 at 12:53

marom

5,064
10
14

1

Not so OK, they want "descending order". – p-a-o-l-o Nov 21 '17 at 13:19

JojOatXGME · Answer 2 · 2017-11-21T14:33:10.007

If I understand you correctly, you want to get a soted list of indices. One solution is to create an unordered list of indices of all elements and sort it.

int array[] = {2, 4, 3, 1};
int indices[] = {0, 1, 2, 3};

std::sort(indices, indices + 4, [&](int a, int b) {
    return array[b] < array[a];
});

Since you asked for a non-C++11-way, you can work around the lambda expression as shown below:

int array[] = {2, 4, 3, 1};
int indices[] = {0, 1, 2, 3};

struct {
    int *array;
    bool operator()(int a, int b) const
    {
        return this->array[b] < this->array[a];
    }
} customLess = {array};

std::sort(indices, indices + 4, customLess);

Both implementations will sort the values of indices but not array itself. The result would look as shown below:

array == {2, 4, 3, 1}
indices == {1, 2, 0, 3}

score 0 · Answer 3 · answered Nov 21 '17 at 12:54

You have to save the initial index somewhere. One solution would be with an struct. Somewhat like this:

struct IndexInt
{
    int index;
    int value;

} typename IndexInt_t

IndexInt_t array[]={{1,2}, {2,4}, {3,3}, {4,1}};

Now you can sort after array[i].value and access the origin index via array[i].index.

Raindrop7 · Accepted Answer · 2017-11-21T13:47:53.480

There's a tricky and easy workaround: First you have an unsorted array so create an array of indexes {0, 1, 2, 3} then use loops to sort the array of values and at the same time swap the elements of array of indexes according to the array of values:

int array[] = {2, 4, 3, 1};
int indexes[] = {0, 1, 2, 3};

for(int i(0); i < 4; i++){
    for(int j(i + 1); j < 4; j++){
        if(array[i] < array[j]){

            //sorting values
            array[i] ^= array[j];
            array[j] ^= array[i];
            array[i] ^= array[j];

            // sorting indexes
            indexes[i] ^= indexes[j];
            indexes[j] ^= indexes[i];
            indexes[i] ^= indexes[j];
        }
    }
}

cout << endl;
for(int i = 0; i < 4; i++)
    cout << array[i] << ", ";
cout << endl;

for(int i = 0; i < 4; i++)
    cout << indexes[i] << ", ";

I used xor to sort the arrays however you can use a temporary variable:

int tmp = array[i]; 
array[i] = array[j];
array[j] = tmp;

tmp = indexes[i];
indexes[i] = indexes[j];
indexes[j] = tmp;

The output:

4, 3, 2, 1,
1, 2, 0, 3,

How do I sort not the elements of an array, but it's indexes?

4 Answers4