javaarrayssortingclass-library

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?


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&tstart=0


Solution

  • 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;
    }