[알고리즘] 계수 정렬(Counting Sort)

계수정렬

• 각 숫자가 몇개 있는지 갯수를 세어서 다른 한 배열에 저장한 후에 정렬을 하는 방식
• 카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다.
• 특정 데이터의 개수를 데이터의 값에 대응하는 위치에 저장
• 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 생성
• 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다.

코드 설계

1. 각 요소의 범위가 1 ~ 7까지인 배열(A)을 읽기
2. 요소의 값의 빈도수(frequency)를 저장
3. 빈도 수를 기준으로 빈도수가 큰 순으로 정렬

코드 구현

    // int[] A = new int[] {1, 5, 4, 6, 5, 7, 1, 4, 4, 2};

    public int[] solution(int[] A) {
        int[] answer = {};

        // key : value로 저장할 수 있는 HashMap 생성
        Map<Integer, Integer> countMap = new HashMap<>();

        // 입력 값 출력
        for(int a : A) {
            countMap.put(a, countMap.getOrDefault(a, 0) + 1);
        }

        // key 값 가져와서 sorting
        List<Integer> sorted = new ArrayList<>(countMap.keySet());
        // 내림차순 정렬 (빈도수가 높은 순으로 정렬)
        Collections.sort(sorted, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return countMap.get(o2).compareTo(countMap.get(o1));
            }
        });

        answer = new int[sorted.size()];
        for(int i = 0 ; i < sorted.size() ; i++) {
            answer[i] = sorted.get(i);
        }

        return answer;
    }

• 과정 값 및 결과 값

// key : frequency
4[3]    1[2]    5[2]    2[1]    6[1]    7[1]
// answer
4    1    5    2    6    7

분석

• 모든 데이터의 크기 범위를 메모리 상에 표현할 수 있다면 복잡도 O(N)