Get array indices after sorting?

Question

Suppose the user enters an array, for example:

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

which I knew about its length

array index :

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

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

newArray will look like this:

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

and newIndex will be:

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

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

Thank you in advance

Answer 1

Do not start array sorting. Sort the index array by passing it to a comparator, which compares the values, using them as indices in the array. So you get newIndex as a result of the sort, and it is trivial to go from there to a sorted array of actual elements.

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

EDIT: Okay, here is an example of a comparator. For simplicity, I assume that you only want to sort the "source" array of strings ... and I will not bother with odd 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 would use it as follows:

 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

A short way to achieve this using the 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 get indexes in sorting order, and above map.keySet () to get strings, or above map.entrySet () to get String-index-Pair.

Answer 4

I did the following based on @Skeet code. I think this is a little more OOPi. I dont know.

 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 a class that implements sorting and indexing with Comparator code for different objects, the objects in the source array must implement the Comparable interface. It seems that many objects of interest have a natural order and already have a Comparable interface.

 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 5

One way to do this is to wrap the source index and country name in a separate class. Then sort the array by name. This way your original indexes will be saved.

Answer 6

What comes at a glance is their juxtaposition

 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 this , and then you can find out their indices 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 7

If there is a script for multiple sorting of primitive float or int arrays with positive values, then a method similar to below gives a 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;