Get the indices of an array after sorting?

Question

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

the index array would be:

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

Now, after sorting it using Arrays.sort(Array);

newArray will be like:

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

and the newIndex will be:

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

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

Answer 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.

Answer 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();

Answer 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.

Answer 4

If having a scenario of repeatedly sorting primitive float or int arrays with positive values, then a method like below yields much better (x3~x4) speed compared to using any comparators:

long time = System.currentTimeMillis();
for (int i = 0; i < iters; i++) {           
    float[] array = RandomUtils.randomFloatArray(-1,  1, 3000);
    long[] valueKeyPairs = new long[array.length]; 
    for (int j = 0; j < array.length; ++j) {
        valueKeyPairs[j] = (((long) Float.floatToIntBits(array[j])) << 32) | (j & 0xffffffffL);
    }
    Arrays.sort(valueKeyPairs);
    /**Then use this to retrieve the original value and index*/
    //long l = valueKeyPairs[j];
    //float value = Float.intBitsToFloat((int) (l >> 32));
    //int index = (int) (l);
}
long millis = System.currentTimeMillis() - time;

Answer 5

I made the following based on @Skeet's code. I think it is a little more OOPie. I dunno.

public static <T extends Comparable<T>> List<Integer> sortIndex(List<T> in) {
    ArrayList<Integer> index = new ArrayList<>();
    for (int i = 0; i < in.size(); i++) {
        index.add(i);
    }

    Collections.sort(index, new Comparator<Integer>() {
        @Override
        public int compare(Integer idx1, Integer idx2) {
            return in.get(idx1).compareTo(in.get(idx2));
        }
    });

    return index;
}

Instead of the class that implements the sorting and indexing having the Comparator code for the different objects coming in, the objects in the original array must implement the Comparable interface. It seems many objects of interest have a natural ordering and have the Comparable interface implemented already.

public static void main(String[] args) {

    List<Integer> a1 = new ArrayList<>(Arrays.asList(2, 3, 9, 4, 1));
    // Just pass in the list to have its indexes sorted by the natural ordering
    List<Integer> idx = sortIndex(a1);

    List<Double> a2 = new ArrayList<>(Arrays.asList(1.0, 5.3, 5.2, -3.1, 0.3));
    idx = sortIndex(a2);

    List<numBits> a3 = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        a3.add(new numBits(i));
    }

    // If you need to sort the indexes of your own object, you must implement
    // the Comparable Interface.
    idx = sortIndex(a3);
}

static class numBits implements Comparable<numBits> {
    private int a;

    public numBits(int i) {
        a = i;
    }

    public String toString() {
        return Integer.toString(a);
    }

    // Sort by the total number of bits in the number.
    @Override
    public int compareTo(numBits that) {
        if (Integer.bitCount(this.a) < Integer.bitCount(that.a))
            return -1;
        if (Integer.bitCount(this.a) > Integer.bitCount(that.a))
            return 1;
        return 0;
    }
}

Answer 6

One way you could do this is to Wrap the original index and country name into a separate Class. Then sort the Array based on the names. This way, your original indexes will be preserved.

Answer 7

What Comes at first Glance is Map them like that

Map <Integer, String> map = new HashMap<Integer, String>();
map.put(0, "France");
map.put(1, "Spain");
map.put(2, "France");

and then sort them by value like that and then you can know their indexes and values (key, values) just print the map

Iterator mapIterator = map.keySet().iterator();  

while (mapIterator .hasNext()) {  
     String key = mapIterator.next().toString();  
     String value = map.get(key).toString();  

     System.out.println(key + " " + value);  
}

Answer 8

i found solution.

List<String> a = {b, a, d, c};
List<Integer> b = {2, 1, 4, 3};

and if a sort

private void setsortb() {
List<String> beforeA = new ArrayList<>();
List<Integer> beforeB = new ArrayList<>();
beforeA.addAll(a);
beforeB.addAll(b);
a.sort();//change like this {a, b, c, d}

for(int i = 0; i < beforeA.size(); i++) {
int index = beforeA.indexOf(a.get(i));
b.set(i, beforeB.get(i));
}
}

like this

result

a = {a, b, c, d}
b = {1, 2, 3, 4}