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

Question

The problem: Consder 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?

---

Update:

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.

http://forums.java.net/jive/thread.jspa?threadID=62657&amp;tstart=0

Answer 1

I guess the easiest way to do it is to index the array as it is created. You would need key,value pairs. If the index is a separate structure, then i cant see how you could do it without other objects (interested in seeing it though)

Answer 2

Create a TreeMap of values to indices

    float[] array = new float[]{};
    Map<Float, Integer> map = new TreeMap<Float, Integer>();
    for (int i = 0; i < array.length; ++i) {
        map.put(array[i], i);
    }
    Collection<Integer> indices = map.values();

indices will be the sorted by the floats they point to, the original array is untouched. Converting the Collection<Integer> to a int[] is left as an exercise if it's really necessary.

EDIT: As noted in the comments, this approach does not work if there are duplicate values in the float array. This can be addressed by making the Map<Float, Integer> into a Map<Float, List<Integer>> though this will complicate the inside of the for loop and the generation of the final collection slightly.

Answer 3

With Functional Java:

import static fj.data.Array.array;
import static fj.pre.Ord.*;
import fj.P2;

array(d).toStream().zipIndex().qSort(p2Ord(doubleOrd, intOrd))
  .map(P2.<Double, Integer>__2()).toArray();

Answer 4

Convert the input to a pair class like the one below and then sort this using Arrays.sort(). Arrays.sort() ensures that original order is preserved for equal values like Matlab does. You then need to convert the sorted result back to the separate arrays.

class SortPair implements Comparable<SortPair>
{
  private int originalIndex;
  private double value;

  public SortPair(double value, int originalIndex)
  {
    this.value = value;
    this.originalIndex = originalIndex;
  }

  @Override public int compareTo(SortPair o)
  {
    return Double.compare(value, o.getValue());
  }

  public int getOriginalIndex()
  {
    return originalIndex;
  }

  public double getValue()
  {
    return value;
  }

}

Answer 5

I would tailor the quicksort algorithm to perform the exchange operation on multiple arrays at the same time: the index array and the value array. For example (based on this quicksort):

public static void quicksort(float[] main, int[] index) {
    quicksort(main, index, 0, index.length - 1);
}

// quicksort a[left] to a[right]
public static void quicksort(float[] a, int[] index, int left, int right) {
    if (right <= left) return;
    int i = partition(a, index, left, right);
    quicksort(a, index, left, i-1);
    quicksort(a, index, i+1, right);
}

// partition a[left] to a[right], assumes left < right
private static int partition(float[] a, int[] index, 
int left, int right) {
    int i = left - 1;
    int j = right;
    while (true) {
        while (less(a[++i], a[right]))      // find item on left to swap
            ;                               // a[right] acts as sentinel
        while (less(a[right], a[--j]))      // find item on right to swap
            if (j == left) break;           // don't go out-of-bounds
        if (i >= j) break;                  // check if pointers cross
        exch(a, index, i, j);               // swap two elements into place
    }
    exch(a, index, i, right);               // swap with partition element
    return i;
}

// is x < y ?
private static boolean less(float x, float y) {
    return (x < y);
}

// exchange a[i] and a[j]
private static void exch(float[] a, int[] index, int i, int j) {
    float swap = a[i];
    a[i] = a[j];
    a[j] = swap;
    int b = index[i];
    index[i] = index[j];
    index[j] = b;
}

Answer 6

The more general case of Jherico's answer that allows duplicate values would be this:

// Assuming you've got: float[] array; defined already

TreeMap<Float, List<Integer>> map = new TreeMap<Float, List<Integer>>();
for(int i = 0; i < array.length; i++) {
    List<Integer> ind = map.get(array[i]);
    if(ind == null){
        ind = new ArrayList<Integer>();
        map.put(array[i], ind);
    }
    ind.add(i);
}

// Now flatten the list
List<Integer> indices = new ArrayList<Integer>();
for(List<Integer> arr : map.values()) {
    indices.addAll(arr);
}

Answer 7

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 Float.compare(data[o1], data[o2]);
    }
});