CODEWITHSUNDEEP
javaarrayssortingindexing
user1932739
user1932739

Reputation: 101

Java: array of sorted indexes

Quick question: I have an array double[]array=new double [10] in which there are random doubles, say between 0 and 20. What i want is get another array int []resultingArray=new int [array.length] that each value int is the index of a value double of the array[] sorted form the biggest number to the smallest. Since my english sucks here is a "diagram":

array = (2, 6, 3) _____ resultingArray = (1, 2, 0)

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.

Upvotes: 3

Views: 5628

Answers (6)

Peter Lawrey
Peter Lawrey

Reputation: 533880

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.

Upvotes: 0

Daniel Fischer
Daniel Fischer

Reputation: 183978

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.

Upvotes: 0

fge
fge

Reputation: 121840

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.

Upvotes: 1

arshajii
arshajii

Reputation: 129572

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]

Upvotes: 0

Kent
Kent

Reputation: 195269

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

Upvotes: 0

Pragmateek
Pragmateek

Reputation: 13408

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)));
    }
}

Upvotes: 0

Related Questions