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?
sort(long[], int, int) method sorts the specified range of the specified array of longs into ascending numerical order. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive.
It works by recursively calling itself with smaller and smaller copies of the beginning of the list to see if they are sorted. The base case is a single element, which is always sorted. For other cases, it compares the last element to the maximum element from the previous elements in the list.
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; }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With