Best way to find item position in unsorted array after sorting

Question

We have an unsorted array, we need to print the position of each element, assuming that it will be sorted.

for example: we have an array.

arr[] = {3, 2, 6, 1, 4} //index: 1 2 3 4 5 Index of elements 1-based //Sorted {1, 2, 3, 4, 6} List after sorting //index: 4 2 1 5 3 Index of elements from original array 

he should print

4 2 1 5 3

Answer 1

Sort the array {1, 2, 3, ..., N} in parallel with this array. Thus, in your example, {3, 2, 6, 4} will be sorted, with each swap affecting this array and the array {1, 2, 3, 4} . The end result will be {2, 3, 4, 6} for the first array and {2, 1, 4, 3} for the second; the last array is the answer to your question.

If this is not clear, here is a longer example:

 5 2 1 4 3 1 2 3 4 5 2 5 1 4 3 2 1 3 4 5 2 1 5 4 3 2 3 1 4 5 2 1 4 5 3 2 3 4 1 5 2 1 4 3 5 2 3 4 5 1 2 1 3 4 5 2 3 5 4 1 1 2 3 4 5 3 2 5 4 1 

I used bubble sorting :-) to sort the top row and just swap the bottom row parallel to the top row. But the idea should work with any sorting method: just manipulate the bottom line in parallel with the operations (swaps or something else) that you perform on the top line.

Answer 2

Store the data and index of the array element as a pair and sort the array of pairs. Now print only part of the index.

 // Original array int arr[] = {3, 2, 6, 4}; // Size of original array const int sz = static_cast<int>(sizeof arr / sizeof arr[0]); // Array of pair {.first = item, .second = 1-based index std::vector< pair<int, int> > vp(sz); // std::array if size is fixed for(int i = 0; i < sz; ++i) vp[i] = make_pair(arr[i], i + 1); /* Can be done in a more fancy way using std::transform + lambda */ // Sort the array, original array remains unchanged std::sort(vp.begin(), vp.end()); // Print the result for(int i = 0; i < sz; ++i) cout << ' ' << vp[i].second; 

Living code

Temporary code complexity: O (N log N) , where N is the number of elements in the array

---

From the comment, since the value of N is large and all numbers are different, you can use the following snippet

 int maxn = maximum value of a number; int positions[maxn] = {0}; // Or choose a sparse array with constant update time int arr[] = {3, 2, 6, 4}; const int sz = static_cast<int>(sizeof arr / sizeof arr[0]); for(int i = 0; i < sz; ++i) { assert( arr[i] >= 0 ); position[ arr[i] ] = i + 1; } for(int i = 0; i < maxn; ++i) { if(position[i]) cout << ' ' << position[i]; } 

Living code

Temporary code complexity: O (N) , where N is the maximum number

Answer 3

You can create a perm array that contains the index of the first arr array, and sort this perm array based on the value of arr

 int arr[] = {3, 2, 6, 4}; int compare (const void * a, const void * b) { int diff = arr[*(int*)a] - arr[*(int*)b]; return diff; } int main(void) { int perm[4], i; for (i = 0 ; i != 4 ; i++) { perm[i] = i ; } qsort (perm, 4, sizeof(int), compare); for (i = 0 ; i != 4 ; i++) { printf("%d ", perm[i] + 1); } return 0; } 

Output:

 2 1 4 3 

Link http://ideone.com/wH1giv

Answer 4

I don't know if this is the most efficient way, but I would create an array of nodes . Each node has value and pos . Then sort by the value from which you can get the position.

 struct node{ int value; int pos; } 

As I said, it will work, but I doubt that this is the most effective way

Answer 5

I do not know C ++, so I can not give you the exact code, but the pseudo code should work below.

 1. Given input array 2. Take another empty array of equal length (This will be the output array of positions) 3. Fill the output array with zero (initially all values will be zero in the array) 4. while (output array does not contain zero) a. loop through input array and find maximum number in it. b. get the position of maximum number from input array and set it at the same position in output array c. ignore the element in input array ,if corresponding index in output array is not zero (if it is not zero, then it means index is already filled up) 5. Repeat setps a,b and c until all the elements in output array becomes non zero 

The complexity of this algorithm is O (n2). I have not found a better way than this. Please let me know if you have any questions.

Answer 6

You can use the following:

 template <typename T> std::vector<std::size_t> compute_ordered_indices(const std::vector<T>& v) { std::vector<std::size_t> indices(v.size()); std::iota(indices.begin(), indices.end(), 0u); std::sort(indices.begin(), indices.end(), [&](int lhs, int rhs) { return v[lhs] < v[rhs]; }); return indices; } 

Live demo