Index of each element after sorting

Question

If we have array of element, what is the efficient way to calculate index of each element after sorting that array? is there any way to efficiently reuse sort function in c++ or java?

for example:

double[] array=[".2",".6",".3",".5",".1"];

I want something like this:

         ans=  [  1,   4,   2,   3,   0 ];

that's because after sort .2 place in index 1, .6 place in index 4, .3 place in index 2 and so on.

possible duplicate of [How to sort an array and keep track of the index in java](http://stackoverflow.com/questions/23587314/how-to-sort-an-array-and-keep-track-of-the-index-in-java) — Tim Biegeleisen, Jun 30 '15 at 05:44
that's a different question. I need to know index of each element after sort, but those algorithms provide index of each element in original array. — Hossein Nasr, Jun 30 '15 at 05:52
You need to encapsulate the original index of each element before the sort so that you can access it after the sort. — Tim Biegeleisen, Jun 30 '15 at 05:54
It won't help because in want to access rank of element by `O(1)` after sorting. I don't want to search for the element each time. — Hossein Nasr, Jun 30 '15 at 05:59

score 0 · Answer 1 · answered Jun 30 '15 at 06:53

This will accomplish what you are looking for in O(n log n), there most likely is a better way:

double[] arr = {0.2, 0.6, 0.3, 0.5, 0.1};
Integer[] intermediateIndices = new Integer[arr.length];
Integer[] finalIndices = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
  intermediateIndices[i] = i;
  finalIndices[i] = i;
}

Arrays.sort(intermediateIndices, new Comparator<Integer>() {
  @Override
  public int compare(Integer o1, Integer o2) {
    return Double.compare(arr[o1], arr[o2]);
  }
});

Arrays.sort(finalIndices, new Comparator<Integer>() {
  @Override
  public int compare(Integer o1, Integer o2) {
    return intermediateIndices[o1] - intermediateIndices[o2];
  }
});

System.out.println(Arrays.toString(intermediateIndices));
System.out.println(Arrays.toString(finalIndices));

// [4, 0, 2, 3, 1]
// [1, 4, 2, 3, 0]

Index of each element after sorting

1 Answers1