nLogn 보다 빠른 시간 복잡도로 정렬이 가능한 Counting Sort 정리

Counting Sort 는 O(n+k) 의 시간 복잡도와 O(n+k) 의 공간복잡도를 이용해서 정렬을 할 수 있는 알고리즘이다. 여기서 k는 가장 큰 키 값을 나타낸다.

일반적으로 "비교 기반" 의 정렬 알고리즘은 O(n log N) 이 가장 효율적인 알고리즘인 것이 수학적으로 증명되었으나, 

Counting Sort 는 비슷한 종류의 Radix Sort 와 마찬가지로 비교 기반의 알고리즘이 아니기 때문에 정렬에 있어 O(n) 의 시간 복잡도를 가질 수 있다.

단, Counting sort 는 비교 기반의 정렬 알고리즘이 아니기 때문에 다소 제약 사항이 존재한다.

Counting sort 는 간단하게 설명해서는 구별되는 키(Distinct Key) 와 해당 키를 Counting 함으로써 이루어지기 때문에, 해당 키값(일반적으로 정수)을 저장할 수 있을 만큼의 Hash table 을 요한다.

말이 Hash table 이지, 키 값을 구별할 수 있는 index table 을 counting array 형태로 사용해도 무방하다.

아래는 Counting sort에 대한 간단한 로직과 구현이다.

(1) Element 의 빈도수(Frequency)를 카운팅(Count)한다.

(2) 카운팅한 빈도수들을 누적합 형태로 정리한다.

(3) Input array 를 순회하며 해당 요소들의 카운트를 차감시키면서 Index 에 배치한다.

    public static int[] countingSort(int[] arr, int noMax) {

        int n = arr.length;

        int[] counts = new int[noMax + 1];

        int[] results = new int[n];

        for (int i = 0; i < n; i++) {

            counts[arr[i]]++;

        }

        for (int i = 1; i <= noMax; i++) {

            counts[i] += counts[i - 1];

        }

        for (int i = n - 1; i >= 0; i--) {

            results[counts[arr[i]] - 1] = arr[i];

            --counts[arr[i]];

        }

        return results;

    }

Counting Sort 는 위와 같이 Element 의 크기에 영향을 받으며, 만약 정렬하고자 하는 요소들 간에 데이터 간격이 Sparse 하다면 불필요한 메모리 사용을 야기한다.

만약 n이 작은 상황이지만 k값이 크다면 당연히 일반 비교 기반 정렬 알고리즘 보다 느리게 된다.

데이터를 잘 분석해서 사용할 만한 경우에 사용하는 것이 필요하다.