Java Array sort: Quick way to get a sorted list of indices of an array


The problem: Consider the following floats[]:

d[i] =     1.7 -0.3  2.1  0.5

What I want is an array of int[] that represents the order of the original array with indices.

s[i] =       1    3    0    2
d[s[i]] = -0.3  0.5  1.7  2.1

Of course it could be done with a custom comparator, a sorted set of custom objects, or by simply sorting the array and then searching for the indices in the original array (shudder).

What I am in fact looking for is the equivalent for the second return argument of Matlab's sort function.

Is there an easy way to do that (<5 LOC)? May there be a solution that does not need to allocate a new object for each element?


Thanks for your responses. Unfortunately, none of what has been proposed so far resembles the simple and efficient solution I was hoping for. I therefore openened a thread in the JDK feedback forum, proposing the addition of a new class-library function to address the issue. Lets see what Sun/Oracle thinks about the issue.

Best Solution

Simple solution to create an indexer array: sort the indexer comparing the data values:

final Integer[] idx = { 0, 1, 2, 3 };
final float[] data = { 1.7f, -0.3f,  2.1f,  0.5f };

Arrays.sort(idx, new Comparator<Integer>() {
    @Override public int compare(final Integer o1, final Integer o2) {
        return[o1], data[o2]);