Best way to find position of element in unsorted array after it gets sorted

Question

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

e.g.: 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

it should print

4 2 1 5 3

Answer 1

Sort the array {1, 2, 3, ..., N} in parallel with the given array. So in your example, {3, 2, 6, 4} would be sorted, with every swap affecting that array and the array {1, 2, 3, 4}. The final result would be {2, 3, 4, 6} for the first array and {2, 1, 4, 3} for the second; the latter array is the answer to your question.

In case that isn't clear, here's 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 sort :-) to sort the top row, and just swapped the bottom row in parallel with the top row. But the idea should work with any sorting method: just manipulate the bottom row in parallel with the operations (swaps or whatever) you are performing on the top row.