c++ - How to obtain the index permutation after the sorting

Question

Given an array arr = {5, 16, 4, 7}, we can sort it through sort(arr, arr+sizeof(arr)/sizeof(arr[0])). so now the array arr = {4, 5, 7, 16} and the permutation index for the sorted array is {2, 0, 3, 1}. In other words, the arr[2] in the original array is now the smallest element in the sorted array in position 0.

Is there an efficient way so that we can get the permutation index?

Thank you

Answer 1

Create an array of indexes, fill it with numbers 0..N-1, and sort it using a custom comparator. The comparator should compare items from the original array at indexes lhs and rhs. Sorting the array of indexes this way reorders them as a permutation:

vector<int> data = {5, 16, 4, 7};   
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
    index[i] = i;
}
sort(index.begin(), index.end(),
    [&](const int& a, const int& b) {
        return (data[a] < data[b]);
    }
);
for (int i = 0 ; i != index.size() ; i++) {
    cout << index[i] << endl;
}

This prints 2, 0, 3, 1

Here is a demo on ideone.

Note: you can use index to retrieve the data in sorted order:

for (int i = 0 ; i != index.size() ; i++) {
    cout << data[index[i]] << endl;
}