Eng.Fouad Eng.Fouad - 1 year ago 99
Java Question

Get the indices of an array after sorting?

Suppose the user enter an array, for example:

Array = {France, Spain, France, France, Italy, Spain, Spain, Italy}

which I did know the length of it

array would be:

index = {0, 1, 2, 3, 4, 5, 6, 7}

Now, after sorting it using

will be like:

newArray = {France, France, France, Italy, Italy, Spain, Spain, Spain}

and the
will be:

newIndex = {0, 2, 3, 4, 7, 1, 5, 6}

The problem is: how can I find the
from the input Array?

Thanks in advance

Answer Source

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;

    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.