Lowering Time Complexity of Producing Rank Array

Question

public Ranking(String[] names, float[] scores) { nameTest = new Cities[names.length]; rankTest = new Cities[names.length]; city = new Cities[names.length]; scoreRanks = new Float[scores.length]; for (int i = 0; i < scores.length - 1; i++) { if (scores[i] == scores[i + 1]) throw new IllegalArgumentException(); } if (names == null || scores == null) throw new NullPointerException(); if (names.length != scores.length) throw new IllegalArgumentException();

        for (int p = 0; p < scoreRanks.length; p++) {
            scoreRanks[p] = scores[p];
        }
        int[] ranking = new int[names.length];
        for (int k = 0; k < ranking.length; k++) {
            ranking[this.smallestIndex()] = k + 1;
        }
        for (int i = 0; i < ranking.length; i++) {
            city[i] = new Cities(names[i], ranking[i]);
            nameTest[i] = new Cities(names[i], ranking[i]);
            rankTest[i] = new Cities(names[i], ranking[i]);
        }
        Arrays.sort(nameTest, Cities.BY_NAME);
        Arrays.sort(rankTest, Cities.BY_RANK);
        for (int i = 0; i < names.length - 1; i++) {
            if (nameTest[i].getName().equals(nameTest[i + 1].getName())
                    || nameTest[i].getName() == null
                    || rankTest[i].getRank() == rankTest[i + 1].getRank())
                throw new IllegalArgumentException();
        }
    }

    public int smallestIndex() {
        float smallest = 0.0f;
        int i;
        for (i = 0; i < scoreRanks.length; i++) {
            if (scoreRanks[i] > 0.0f) {
                smallest = scoreRanks[i];
                break;
            } else
                continue;
        }
        int j = 1;
        while (j < scoreRanks.length) {
            if (scoreRanks[j] < smallest && scoreRanks[j] != 0.0f) {
                smallest = scoreRanks[j];
                i = j;
            }
            j++;
        }
        scoreRanks[i] = 0.0f;
        return i;
    }

This is my ranking constructor. Currently, the call to smallestIndex() inside the for loop bumps it up to O(n^2) time, but I need it to run in no more than O(n log n) time.

What this does is takes an array of Scores and names. Then the spot with the LOWEST score will be rank 1, next lowest is rank 2 so on and so forth. Then I can create Cities objects where names[i] corresponds with ranking[i].

Hope that makes sense. Buy yeah I don't get what I can do to get the same result but in O(n log n) time. My code works perfectly, it is just too slow I guess :(.

Also, would O(2n log n + 5n) boil down to O(n log n)?

Answer 1

From your description, basically you want to sort the list based on increasing score. Examining your code in smallestIndex, it seems that you really are doing that in a very inefficient way. If we are to keep that method, I suggest in changing scoreRanks[i] = 0.0f into scoreRanks[i] = Float.MAX_VALUE and simplify the method by just looping once.

But to do your task efficiently, I suggest removing the smallestIndex entirely. I see that you are already using Arrays.sort with custom comparators. You can solve your task efficiently by simply using the same method. You can create custom Comparator as explained in this question: Get the indices of an array after sorting?

class ArrayIndexComparator implements Comparator<Integer>
{
    private Float[] scores;

    public ArrayIndexComparator(float[] scores)
    {
        this.scores = new Float[scores.length];
        for(int i=0; i<scores.length; i++){
            this.scores[i] = scores[i];
        }
    }

    public Integer[] createIndexArray()
    {
        Integer[] indexes = new Integer[scores.length];
        for (int i = 0; i < scores.length; i++)
        {
            indexes[i] = i;
        }
        return indexes;
    }

    @Override
    public int compare(Integer index1, Integer index2)
    {
        // Autounbox from Integer to int to use as array indexes
        return scores[index1].compareTo(scores[index2]);
    }

    public static void main(String[] args){
        float[] scoreRanks = new float[]{2.0f,3.0f,1.0f};
        ArrayIndexComparator comparator = new ArrayIndexComparator(scoreRanks);
        Integer[] indexes = comparator.createIndexArray();
        Arrays.sort(indexes, comparator);
        int[] ranking = new int[indexes.length];
        for (int i = 0; i < ranking.length; i++) {
            ranking[indexes[i]] = i + 1;
        }
        for (int i = 0; i < ranking.length; i++){
            System.out.println(ranking[i]+" "+scoreRanks[i]);
        }
        // Will print:
        // 2.0 2
        // 3.0 3
        // 1.0 1
    }
}

public Ranking(String[] names, float[] scores) {
    nameTest = new Cities[names.length];
    rankTest = new Cities[names.length];
    city = new Cities[names.length];
    scoreRanks = new Float[scores.length];
    for (int i = 0; i < scores.length - 1; i++) {
        if (scores[i] == scores[i + 1])
            throw new IllegalArgumentException();
    }
    if (names == null || scores == null)
        throw new NullPointerException();
    if (names.length != scores.length)
        throw new IllegalArgumentException();
    for (int p = 0; p < scoreRanks.length; p++) {
        scoreRanks[p] = scores[p];
    }
    // This is the updated part
    ArrayIndexComparator comparator = new ArrayIndexComparator(scoreRanks);
    Integer[] indexes = comparator.createIndexArray();
    Arrays.sort(indexes, comparator);
    int[] ranking = new int[indexes.length];
    for (int i = 0; i < ranking.length; i++) {
        ranking[indexes[i]] = i + 1;
    }
    // Up until this part
    for (int i = 0; i < ranking.length; i++) {
        city[i] = new Cities(names[i], ranking[i]);
        nameTest[i] = new Cities(names[i], ranking[i]);
        rankTest[i] = new Cities(names[i], ranking[i]);
    }
    Arrays.sort(nameTest, Cities.BY_NAME);
    Arrays.sort(rankTest, Cities.BY_RANK);
    for (int i = 0; i < names.length - 1; i++) {
        if (nameTest[i].getName().equals(nameTest[i + 1].getName())
                || nameTest[i].getName() == null
                || rankTest[i].getRank() == rankTest[i + 1].getRank())
            throw new IllegalArgumentException();
    }
}

This way you will use the sort method in Arrays class, which is O(n log n).