Java: array of sorted indexes

There are a lot of solutions using Maps, I'll propose an alternative using only arrays:

public int[] getIndices(double[] originalArray)
{
    int len = originalArray.length;

    double[] sortedCopy = originalArray.clone();
    int[] indices = new int[len];

    // Sort the copy
    Arrays.sort(sortedCopy);

    // Go through the original array: for the same index, fill the position where the
    // corresponding number is in the sorted array in the indices array
    for (int index = 0; index < len; index++)
        indices[index] = Arrays.binarySearch(sortedCopy, originalArray[index]);

    return indices;
}

It is, however, quite inefficient.

Maybe something like :

import java.util.*;

public class Test
{
    static Integer[] getIndicesInOrder(Integer[] array)
    {
        Integer[] c = array.clone();
        Arrays.sort(c, Collections.reverseOrder());

        List<Integer> l = Arrays.asList(array);

        for (int i = 0; i < array.length; ++i)
        {
            c[i] = l.indexOf(c[i]);
        }

        return c;
    }

    public static void main(String[] args)
    {
        Integer[] array = {2,6,3};

        System.out.println(Arrays.toString(getIndicesInOrder(array)));
    }
}

It's an exam question. The doubles are GPAs from students and it asks for a method that returns an array composed of the IDs (which in my code are the indexes of double[]array) of the students from the best student to the worst.

I would do it with Map. <ID, Doubles>. We cannot directly use TreeMap, because it is sorted by Key. We want to sort by Value(those Doubles). We could do some trick on that however, to make our own comparator impl. to sort the map by values.

I wrote it in a junit test class,

@Test
public void testArray() {
    final double[] array = new double[] { 1.1, 2.2, 3.3, 4.4, 3.3 };
    final int[] result = new int[array.length];

    final Map<Integer, Double> map = new HashMap<Integer, Double>();
    for (int i = 0; i < array.length; i++) {
        map.put(i, array[i]);
    }
    final List<Map.Entry> list = new LinkedList<Map.Entry>(map.entrySet());
    Collections.sort(list, new Comparator() {
        @Override
        public int compare(final Object o1, final Object o2) {
            return 0 - ((Comparable) ((Map.Entry) o1).getValue()).compareTo(((Map.Entry) o2).getValue());
        }
    });
    for (int i = 0; i < list.size(); i++) {

        result[i] = (Integer) list.get(i).getKey();
    } 

    //here we have result, to test it:
    for (final int element : result) {
        System.out.println(element);
    }
}

it prints:

    3
    2
    4
    1
    0

Here's how I would do it:

• Put all of the elements of array in a Map<Integer, Double> that maps the index to the value.

• Put all of the elements of the entrySet() of this map into a list and sort that list by values.

• Form an array out of the keys of the newly sorted list of entries.

public static int[] getIndicesInOrder(double[] array) {
    Map<Integer, Double> map = new HashMap<Integer, Double>(array.length);
    for (int i = 0; i < array.length; i++)
        map.put(i, array[i]);

    List<Entry<Integer, Double>> l = 
                           new ArrayList<Entry<Integer, Double>>(map.entrySet());

    Collections.sort(l, new Comparator<Entry<?, Double>>() {
            @Override
            public int compare(Entry<?, Double> e1, Entry<?, Double> e2) {
                return e2.getValue().compareTo(e1.getValue());
            }
        });

    int[] result = new int[array.length];
    for (int i = 0; i < result.length; i++)
        result[i] = l.get(i).getKey();

    return result;
}

public static void main(String[] args) {
    double[] array = { 1.1, 2.2, 3.3, 4.4, 3.3 };

    System.out.println(Arrays.toString(getIndicesInOrder(array)));
}

[3, 2, 4, 1, 0]

You can use a custom Comparator comparing the values in the grades array at the respective indices,

import java.util.*;

public class GradeComparator implements Comparator<Integer> {
    private double[] grades;
    public GradeComparator(double[] arr) {
        grades = arr;
    }
    public int compare(Integer i, Integer j) {
        return Double.compare(grades[j], grades[i]);
    }
}

and sort the index array using that Comaprator:

import java.util.*;

public class SortGrades {
    public static void main(String[] args) {
        double[] grades = { 2.4, 6.1, 3.9, 4.8, 5.5 };
        Integer[] ranks = new Integer[grades.length];
        for(int i = 0; i < ranks.length; ++i) {
            ranks[i] = i;
        }
        Comparator<Integer> gc = new GradeComparator(grades);
        Arrays.sort(ranks, gc);
        for(int i = 0; i < ranks.length; ++i) {
            System.out.println((i+1) + ": " + ranks[i] + ", grade: " + grades[ranks[i]]);
        }
    }
}

Outputs

1: 1, grade: 6.1
2: 4, grade: 5.5
3: 3, grade: 4.8
4: 2, grade: 3.9
5: 0, grade: 2.4

as desired.

If the student's scaore are random you can do this (which doesn't make much sense in the real world as you cannot/do not score student to an accuracy of exactly 15 digits ;)

public static int[] sortWithIndex(double[] results) {
    class ScoreIndex implements Comparable<ScoreIndex> {
        final double score;
        final int index;

        ScoreIndex(double score, int index) {
            this.score = score;
            this.index = index;
        }

        @Override
        public int compareTo(ScoreIndex o) {
            int cmp = Double.compare(score, o.score);
            return cmp == 0 ? Integer.compare(index, o.index) : cmp;
        }
    }
    List<ScoreIndex> list = new ArrayList<>();
    for (int i = 0; i < results.length; i++) list.add(new ScoreIndex(results[i], i));
    Collections.sort(list);
    int[] indexes = new int[results.length];
    for (int i = 0; i < list.size(); i++) indexes[i] = list.get(i).index;
    return indexes;
}

If you grade students to limit precision, say only < 6 digits you can do

public static void sortWithIndex(double[] results) {
    for(int i = 0; i < results.length; i++)
        results[i] = results[i] * results.length * 1e6 + i;
    Arrays.sort(results);
}

The results now contain all the original values and the index they came from in order of values, with the lower indexes first if there are duplicates.