42

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

Improve this question
6
  • even if this were put into the JDK, something I really doubt would ever happen, it would end up being a static utility method on the Arrays class (or something similar) and would end up being implemented very similar to something below. So why can't you just write the function? Commented Jun 12, 2009 at 3:36
  • What is the problem with a custom comparator as a solution? I may be misunderstanding the approach this implies in your mind. Commented Jun 12, 2009 at 3:38
  • Maybe I'm not looking hard enough, but for what I know there is no way to use a Comparator without boxing every element on each call to the Comparator. For an array of n floats that would mean 2*n*log(n) Floats for the garbage collector. With n=10000 that means 80000 pieces of garbage. I would much prefer a static utility method in the Arrays class. If I didn't care about the garbage, I could have used a TreeMap or something in the first place. Commented Jun 17, 2009 at 18:39
  • This is so useful and I wish you could do it in Java. In R you can just use the rank() function. Commented Sep 30, 2010 at 1:13
  • If you have less than 5000 numbers, just use bubble sort. It's easy to read, short, and fast enough. Commented Nov 17, 2011 at 14:26

15 Answers 15

Reset to default
32

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]);
    }
});
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Quite elegant, but uses an unfortunate amount autoboxing. I therefore suspect it's not as efficient as kd304's answer. It's simpler though.
Try to speed test it. If the integers are small, not much autoboxing will be used. And java's sort is more optimized than kd304's.
Definitely what I was looking for. The final is a minor drawback
@keyser why is final a drawback?
@NeoMHacker It's a requirement since we are using it in an anonymous inner class, not much trouble in this case since we are not modifying the data array anyway. See stackoverflow.com/q/4162531/209882
23

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.

Improve this answer

3 Comments

precisely the mapping I was putting together.
Uses an unfortunate amount of autoboxing, but does the trick. +1
The flaw with this approach is that is does not handle duplicate float values.
19

Using Java 8 features ( without extra library) , concise way of achieving it.

int[] a = {1,6,2,7,8}
int[] sortedIndices = IntStream.range(0, a.length)
    .boxed().sorted((i, j) -> Integer.compareTo(a[i], a[j]))
    .mapToInt(ele -> ele).toArray();
Improve this answer

4 Comments

great. what if I have a list or array of elements on which a[i] - a[j] is not allowed?
You can do compareTo docs.oracle.com/javase/7/docs/api/java/lang/…
edited the answer to Integer.compareTo as a[i] - b[i] can cause integer overflow.
b[i] should be a[j] but that's too small to be an edit.
18

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;
}
Improve this answer

3 Comments

Even though far from the desired <= 5 LOC requirement, it's the only solution offered so far, that maintains reasonable performance characteristic. Sorry folks :-(
This is very sad. I have the same problem, and this is the only acceptable solution for large data sets.
But this solution modifies the data array. Normally the point of sorting an index is to avoid modifying the data order. To make it read-only, don't swap the data in exch() and replace each a[x] with a[index[x]].
7

With Functional Java:

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

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

3 Comments

Don't take this the wrong way... but - wow! Totally unreadable code! Sorry - just couldn't resist :-) It does meet the <5 LOC requirement though - including the imports - very impressive!
Unreadable how? Let's read it. Take your array to a stream, pair (zip) each element with its index, quicksort them by pair order (by the double first, then the int), get the second half of each pair, and then take all that to an array. Easy!
It's only unreadable if you're new to functional programming. This kind of thing is perfectly normal in functional languages. Can this be done in Java 8 without a 3rd party library?
3

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);
}
Improve this answer

2 Comments

I think map.put(array[i], ind); should be placed after ind.add(i);
@lizzie it works as is, because ind holds the location of the list, and the thing being updated by ind.add will be the same as the thing in the map.
2

The best solution would be along the lines of C's qsort, which allows you to specify functions for compare and swap, so qsort needn't be aware of the type or organization of the data being sorted. Here is one you can try. Since Java doesn't have functions, use the Array inner class to wrap the array or collection to be sorted. Then wrap that in an IndexArray and sort. The result of getIndex() on the IndexArray will be an array of indices as described in the JavaDoc.

public class QuickSortArray {

public interface Array {
    int cmp(int aindex, int bindex);
    void swap(int aindex, int bindex);
    int length();
}

public static void quicksort(Array a) {
    quicksort(a, 0, a.length() - 1);
}

public static void quicksort(Array a, int left, int right) {
    if (right <= left) return;
    int i = partition(a, left, right);
    quicksort(a, left, i-1);
    quicksort(a, i+1, right);
}

public static boolean isSorted(Array a) {
    for (int i = 1, n = a.length(); i < n; i++) {
        if (a.cmp(i-1, i) > 0)
            return false;
    }
    return true;
}

private static int mid(Array a, int left, int right) {
    // "sort" three elements and take the middle one
    int i = left;
    int j = (left + right) / 2;
    int k = right;
    // order the first two
    int cmp = a.cmp(i, j);
    if (cmp > 0) {
        int tmp = j;
        j = i;
        i = tmp;
    }
    // bubble the third down
    cmp = a.cmp(j, k);
    if (cmp > 0) {
        cmp = a.cmp(i, k);
        if (cmp > 0)
            return i;
        return k;
    }
    return j;
}

private static int partition(Array a, int left, int right) {
    int mid = mid(a, left, right);
    a.swap(right, mid);
    int i = left - 1;
    int j = right;

    while (true) {
        while (a.cmp(++i, right) < 0)
            ;
        while (a.cmp(right, --j) < 0)
            if (j == left) break;
        if (i >= j) break;
        a.swap(i, j);
    }
    a.swap(i, right);
    return i;
}

public static class IndexArray implements Array {
    int[] index;
    Array a;

    public IndexArray(Array a) {
        this.a = a;
        index = new int[a.length()];
        for (int i = 0; i < a.length(); i++)
            index[i] = i;
    }

    /**
     * Return the index after the IndexArray is sorted.
     * The nested Array is unsorted. Assume the name of
     * its underlying array is a. The returned index array
     * is such that a[index[i-1]] <= a[index[i]] for all i
     * in 1..a.length-1.
     */
    public int[] index() {
        int i = 0;
        int j = index.length - 1;
        while (i < j) {
            int tmp = index[i];
            index[i++] = index[j];
            index[j--] = tmp;
        }
        int[] tmp = index;
        index = null;
        return tmp;
    }

    @Override
    public int cmp(int aindex, int bindex) {
        return a.cmp(index[aindex], index[bindex]);
    }

    @Override
    public void swap(int aindex, int bindex) {
        int tmp = index[aindex];
        index[aindex] = index[bindex];
        index[bindex] = tmp;
    }

    @Override
    public int length() {
        return a.length();
    }

}
Improve this answer

Comments

2 
public static int[] indexSort(final double[] v, boolean keepUnsorted) {
    final Integer[] II = new Integer[v.length];
    for (int i = 0; i < v.length; i++) II[i] = i;
    Arrays.sort(II, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Double.compare(v[o1],v[o2]);
        }
    });
    int[] ii = new int[v.length];
    for (int i = 0; i < v.length; i++) ii[i] = II[i];
    if (!keepUnsorted) {
        double[] clon = v.clone();
        for (int i = 0; i < v.length; i++) v[i] = clon[II[i]];
    }
    return ii;
}
Improve this answer

2 Comments

It would be better if you added a small explanation to this code.
nice! i liked this one!
0

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

}

Improve this answer

Comments

0

Another non-simple solution. Here's a merge sort version which is stable and doesn't modify the source array, though the merge requires extra memory.

public static int[] sortedIndices(double[] x) {
    int[] ix = new int[x.length];
    int[] scratch = new int[x.length];
    for (int i = 0; i < ix.length; i++) {
        ix[i] = i;
    }
    mergeSortIndexed(x, ix, scratch, 0, x.length - 1);
    return ix;
}

private static void mergeSortIndexed(double[] x, int[] ix, int[] scratch, int lo, int hi) {
    if (lo == hi)
        return;
    int mid = (lo + hi + 1) / 2;
    mergeSortIndexed(x, ix, scratch, lo, mid - 1);
    mergeSortIndexed(x, ix, scratch, mid, hi);
    mergeIndexed(x, ix, scratch, lo, mid - 1, mid, hi);
}

private static void mergeIndexed(double[] x, int[] ix, int[] scratch, int lo1, int hi1, int lo2, int hi2) {
    int i = 0;
    int i1 = lo1;
    int i2 = lo2;
    int n1 = hi1 - lo1 + 1;
    while (i1 <= hi1 && i2 <= hi2) {
        if (x[ix[i1]] <= x[ix[i2]])
            scratch[i++] = ix[i1++];
        else
            scratch[i++] = ix[i2++];
    }
    while (i1 <= hi1)
        scratch[i++] = ix[i1++];
    while (i2 <= hi2)
        scratch[i++] = ix[i2++];
    for (int j = lo1; j <= hi1; j++)
        ix[j] = scratch[j - lo1];
    for (int j = lo2; j <= hi2; j++)
        ix[j] = scratch[(j - lo2 + n1)];
}
Improve this answer

Comments

0 
//Here index array(of length equal to length of d array) contains the numbers from 0 to length of d array   
      public static Integer [] SortWithIndex(float[] data, Integer [] index)
    {
    int len = data.length;
    float temp1[] = new float[len];
    int temp2[] = new int[len];



         for (int i = 0; i <len; i++) {


                for (int j = i + 1; j < len; j++) {


                  if(data[i]>data[j])
                  {
                    temp1[i] = data[i];
                    data[i] = data[j];
                    data[j] = temp1[i];



                    temp2[i] = index[i];
                    index[i] = index[j];
                    index[j] = temp2[i];

                    }
                  }

        }

        return index;

    }
Improve this answer

Comments

0

I would do something like this:

public class SortedArray<T extends Comparable<T>> {
    private final T[] tArray;
    private final ArrayList<Entry> entries;

    public class Entry implements Comparable<Entry> {
        public int index;

        public Entry(int index) {
            super();
            this.index = index;
        }

        @Override
        public int compareTo(Entry o) {
            return tArray[index].compareTo(tArray[o.index]);
        }
    }

    public SortedArray(T[] array) {
        tArray = array;
        entries = new ArrayList<Entry>(array.length);
        for (int i = 0; i < array.length; i++) {
            entries.add(new Entry(i));
        }
        Collections.sort(entries);
    }

    public T getSorted(int i) {
        return tArray[entries.get(i).index];

    }

    public T get(int i) {
        return tArray[i];
    }
}
Improve this answer

Comments

0

Below is a method based on Insertion Sort

public static int[] insertionSort(float[] arr){
    int[] indices = new int[arr.length];
        indices[0] = 0;
        for(int i=1;i<arr.length;i++){
            int j=i;
            for(;j>=1 && arr[j]<arr[j-1];j--){
                    float temp = arr[j];
                    arr[j] = arr[j-1];
                    indices[j]=indices[j-1];
                    arr[j-1] = temp;
            }
            indices[j]=i;
        }
        return indices;//indices of sorted elements
 }
Improve this answer

Comments

0

I'd like to use this because it is very fast.But I use it for int,you can change it to float.

private static void mergeSort(int[]array,int[] indexes,int start,int end){
    if(start>=end)return;
    int middle = (end-start)/2+start;
    mergeSort(array,indexes,start,middle);
    mergeSort(array,indexes,middle+1,end);
    merge(array,indexes,start,middle,end);
}
private static void merge(int[]array,int[] indexes,int start,int middle,int end){
    int len1 = middle-start+1;
    int len2 = end - middle;
    int leftArray[] = new int[len1];
    int leftIndex[] = new int[len1];
    int rightArray[] = new int[len2];
    int rightIndex[] = new int[len2];
    for(int i=0;i<len1;++i)leftArray[i] = array[i+start];
    for(int i=0;i<len1;++i)leftIndex[i] = indexes[i+start];
    for(int i=0;i<len2;++i)rightArray[i] = array[i+middle+1];
    for(int i=0;i<len2;++i)rightIndex[i] = indexes[i+middle+1];
    //merge
    int i=0,j=0,k=start;
    while(i<len1&&j<len2){
        if(leftArray[i]<rightArray[j]){
            array[k] = leftArray[i];
            indexes[k] = leftIndex[i];
            ++i;
        }
        else{
            array[k] = rightArray[j];
            indexes[k] = rightIndex[j];
            ++j;
        }
        ++k;
    }
    while(i<len1){
        array[k] = leftArray[i];
        indexes[k] = leftIndex[i];
        ++i;++k;
    }
    while(j<len2){
        array[k] = rightArray[j];
        indexes[k] = rightIndex[j];
        ++j;++k;
    }
}
Improve this answer

Comments

-2

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)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.