[Algorithm] 계수 정렬(Counting Sort)

설명

• 데이터 분포도가 한정적일 경우에 한해서 굉장히 빠른 정렬 알고리즘
• 시간 복잡도 : O(N)
• 참고
  • https://youtu.be/n4kbFRn2z9M

예시

• 초기값
  • 3 3 2 2 1 2 5 5 4
• 각 데이터 개수 확인
  • 3(2) 2(3) 1(1) 5(2) 4(1)
• 각 키를 기준으로 정렬
  • 1(1) 2(3) 3(2) 4(1) 5(2)
• 각 개수만큼 반환
  • 1 2 2 2 3 3 4 5 5

코드

public class Solution {
    public static int[] sort(int[] data) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int index = 0;

        for (int number : data) {
            countMap.put(number, countMap.getOrDefault(number, 0) + 1);
        }

        for (int number : countMap.keySet().stream().sorted().collect(Collectors.toList())) {
            for (int i = 0; i < countMap.get(number); i++) {
                data[index++] = number;
            }
        }

        return data;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        Solution.sort(data as int[]) == result

        where:
        data                        | result
        [3, 3, 2, 2, 1, 2, 5, 5, 4] | [1, 2, 2, 2, 3, 3, 4, 5, 5]
    }
}