Study/Algorithm/SpringSprout/Telepathy/Quiz 1. Ranking Service/Counting Sort-based Ranking Service

CountingSortBasedRankingService.java

package study.algorithm.telepathy.sort.quiz.problem1;

public class CountingSortBasedRankingService implements RankingService {
	private final int maxScore;

	public CountingSortBasedRankingService(int maxScore) {
		this.maxScore = maxScore;
	}

	@Override
	public int[] rank(int[] scores) {
		int[] counts = new int[maxScore + 1];
		for (int i = 0; i < scores.length; i++) {
			counts[scores[i]]++;
		}

		int total = 0;
		for (int i = maxScore; i >= 0; i--) {
			int count = counts[i];
			counts[i] = total;
			total += count;
		}

		int[] ranks = new int[scores.length];
		for (int i = 0; i < scores.length; i++) {
			ranks[i] = counts[scores[i]] + 1;
		}
		return ranks;
	}
}

CountingSortBasedRankingServiceTest.java

package study.algorithm.telepathy.sort.quiz.problem1;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.Test;

public class CountingSortBasedRankingServiceTest {
	@Test
	public void testRank() {
		int[] expectedRanks = new int[] { 2, 2, 4, 1 };
		int[] scores = { 80, 80, 60, 100 };

		int maxScore = 100;
		RankingService rankingService = new CountingSortBasedRankingService(
				maxScore);
		int[] ranks = rankingService.rank(scores);

		assertThat(ranks, is(expectedRanks));
	}
}