계수 정렬 (Counting Sort)

Comparison Sort와 계수 정렬

N개의 원소로 이루어진 배열을 정렬하는 경우, 이를 모두 정렬하는 가짓수는 N!이 된다. 일반적으로 Comparison Sort(비교 기반 정렬)의 시간 복잡도는 O(n log n)이다. 이는 비교를 통해 원소들을 정렬할 때, 비교하는 과정이 필수적이기 때문이다. 하지만, O(n log n)의 시간 복잡도를 줄이기 위해 비교를 하지 않는 정렬 방법이 있다. 그 중 하나가 바로 계수 정렬(Counting Sort)이다.

계수 정렬의 과정

계수 정렬은 원소들의 값을 비교하지 않고, 각 원소가 몇 번 등장했는지를 세어 정렬하는 방식이다. 이 정렬 알고리즘은 주어진 배열의 모든 값이 특정 범위 내에 있을 때 매우 효과적으로 작동한다.

• 시간 복잡도: O(n + k) (여기서 n은 배열의 원소 수, k는 배열에서 등장하는 최대값)
• 공간 복잡도: O(k) (k만큼의 배열을 추가로 생성)

계수 정렬의 단계별 설명

1. Counting 배열 생성: 정렬할 배열에서 등장하는 최대값을 기준으로 크기가 k인 배열을 생성한다. 이 배열은 각 원소의 등장 횟수를 저장하는 역할을 한다.

2. Counting 배열 업데이트: 정렬할 배열의 각 원소를 읽어, 해당 값을 인덱스로 하여 Counting 배열의 값을 1씩 증가시킨다.

3. 누적 합 배열 생성: Counting 배열을 순차적으로 누적합 형태로 변환한다. 이 배열을 통해 정렬할 원소의 최종 위치를 결정할 수 있다.

4. 원소 정렬: 정렬할 배열을 역순으로 순회하면서, Counting 배열을 참조하여 정렬된 배열에 값을 채워 넣는다.

계수 정렬의 소스 코드

아래는 계수 정렬의 구현 예제 코드이다.

public class CountingSort {

    public static void countingSort(int[] arr) {
        int n = arr.length;
        int max = getMax(arr); // 배열 내 최대값을 찾음

        // 단계 1: 최대값 크기의 Counting 배열 생성
        int[] counting = new int[max + 1];
        int[] sortedArr = new int[n];

        // 단계 2: 배열 내 각 값의 등장 횟수를 Counting 배열에 기록
        for (int i = 0; i < n; i++) {
            counting[arr[i]]++;
        }

        // 단계 3: Counting 배열을 누적합 배열로 변환
        for (int i = 1; i <= max; i++) {
            counting[i] += counting[i - 1];
        }

        // 단계 4: 배열을 뒤에서부터 순회하며 정렬된 배열을 생성
        for (int i = n - 1; i >= 0; i--) {
            sortedArr[--counting[arr[i]]] = arr[i];
        }

        // 정렬된 배열을 원본 배열에 복사
        System.arraycopy(sortedArr, 0, arr, 0, n);
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }

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

계수 정렬의 활용 및 장단점

• 활용: 계수 정렬은 정렬할 숫자가 특정한 범위 내에 있을 때 특히 유용하다. 예를 들어, 성적을 정렬하거나, 나이를 정렬할 때 사용할 수 있다. 또한, Suffix Array를 구할 때도 활용할 수 있다.

• 장점: O(n)의 시간 복잡도를 가지기 때문에 매우 효율적이다.

• 단점: 배열의 크기가 커질수록 Counting 배열의 크기도 커지게 되며, 이는 메모리 낭비를 초래할 수 있다. 특히, 최대값이 매우 클 경우, 메모리 사용량이 급격히 증가한다.

So...

계수 정렬은 특정 범위 내의 숫자를 정렬할 때 매우 효율적인 알고리즘이다. 하지만, 메모리 사용량이 크기 때문에 최대값이 크거나 범위가 넓을 경우 다른 정렬 알고리즘을 고려하는 것이 좋다. 효율성과 메모리 사용의 균형을 고려하여 적절한 상황에 계수 정렬을 활용할 필요가 있다.