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?

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; }