Get the indices of an array after sorting?

Solution 1:

Don't sort the array to start with. Sort the index array, passing in a comparator which compares values by using them as indexes into the array. So you end up with newIndex as the result of the sort, and it's trivial to go from there to the sorted array of actual items.

Admittedly that means sorting an array of integers in a custom way - which either means using an Integer[] and the standard Java library, or a 3rd party library which has an "IntComparator" interface which can be used in conjunction with a sort(int[], IntComparator) type of method.

EDIT: Okay, here's an example comparator. For the sake of simplicity I'll assume you only want to sort an "original" array of strings... and I won't bother with nullity testing.

public class ArrayIndexComparator implements Comparator<Integer>
{
    private final String[] array;

    public ArrayIndexComparator(String[] array)
    {
        this.array = array;
    }

    public Integer[] createIndexArray()
    {
        Integer[] indexes = new Integer[array.length];
        for (int i = 0; i < array.length; i++)
        {
            indexes[i] = i; // Autoboxing
        }
        return indexes;
    }

    @Override
    public int compare(Integer index1, Integer index2)
    {
         // Autounbox from Integer to int to use as array indexes
        return array[index1].compareTo(array[index2]);
    }
}

You'd use it like this:

String[] countries = { "France", "Spain", ... };
ArrayIndexComparator comparator = new ArrayIndexComparator(countries);
Integer[] indexes = comparator.createIndexArray();
Arrays.sort(indexes, comparator);
// Now the indexes are in appropriate order.

Solution 2:

Concise way of achieving this with Java 8 Stream API,

final String[] strArr = {"France", "Spain", "France"};
int[] sortedIndices = IntStream.range(0, strArr.length)
                .boxed().sorted((i, j) -> strArr[i].compareTo(strArr[j]) )
                .mapToInt(ele -> ele).toArray();

Solution 3:

TreeMap<String,Int> map = new TreeMap<String,Int>();
for( int i : indexes ) {
    map.put( stringarray[i], i );
}

Now iterator over map.values() to retrieve the indexes in sort order, and over map.keySet() to get the strings, or over map.entrySet() to get the String-index-Pairs.