Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to obtain the index permutation after the sorting

Tags:

c++

algorithm

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?

like image 222
q0987 Avatar asked Jul 09 '13 17:07

q0987


People also ask

How do you sort an index array?

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.

How does Bogo sort work?

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.


1 Answers

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; } 
like image 151
Sergey Kalinichenko Avatar answered Sep 18 '22 14:09

Sergey Kalinichenko