[알고리즘] 카운팅 정렬 / 계수 정렬 (Counting Sort)

카운팅 정렬(Counting Sort)이란?

정수나 정수로 표현할 수 있는 자료에 대해 유효한 알고리즘으로, 시간 복잡도가 O(n + k)인 정렬 알고리즘이다. 여기서 n은 배열의 크기이고 k는 배열의 요소 중 최댓값이다. 카운팅 정렬은 주로 범위가 제한된 작은 정수들로 구성된 배열을 정렬하는 데 적합하다.

 

정렬 과정

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력

출처 : https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

 

출처 : https://spagnuolocarmine.github.io/counting-sort.html

 

카운팅 정렬을 사용하면 안되는 상황

• 카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 좋은 성능을 보여주는 알고리즘이다.
• 다만, 카운팅 정렬의 단점은 counting 배열이라는 새로운 배열을 선언해주어야 한다는 점이다.
• array 안에 있는 max 값의 범위에 따라 counting 배열의 길이가 달라지게 된다. 예를 들어 10개의 원소를 정렬하고자 하는데, 수의 범위가 0~1억이라면 메모리가 매우 낭비된다.
• 즉 수열의 길이보다 수의 범위가 극단적으로 크면 많은 메모리가 낭비될 수 있다.

 

구현 코드 예제

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;

        // 배열에서 최댓값과 최솟값 찾기
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            } else if (arr[i] < min) {
                min = arr[i];
            }
        }

        // 빈도수 배열 크기 계산
        int range = max - min + 1;
        int[] count = new int[range];

        // 빈도수 계산
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }

        // 누적 합 계산
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 출력 배열 작성
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 결과를 원래 배열로 복사
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

1. 빈도수 계산 : 입력 배열에서 각 요소가 몇 번 등장하는지 세는 단계이다.
2. 누적 합 계산 : 각 요소의 누적 합을 계산하여 정렬된 배열에서 각 요소의 위치를 결정하는 데 사용한다.
3. 출력 배열 작성 : 입력 배열의 요소들을 올바른 위치에 배치하여 출력 배열을 작성한다.
4. 결과 복사 : 출력 배열을 원래 배열로 복사하여 정렬된 상태를 유지한다.

 

알고리즘 문제를 풀다 보면 카운팅 정렬을 사용하여 풀 수 있는 문제들을 가끔 볼 수 있다. 잘 알고 있다가 멋지게 사용해보고 싶다!😃