Counting Sort

좁은 범용성

주어진 엘리먼트의 크기를 비교해서 정렬하는 일반적인 정렬 알고리즘과는 달리 각 엘리먼트의 개수를 세어 그 위치를 결정하는 정렬 알고리즘이다. 특히 엘리먼트의 값 범위가 좁을 때 매우 높은 퍼포먼스를 보여준다. 하지만 엘리먼트의 개수가 적더라도 값의 범위가 넓은 경우에는 메모리 사용성과 성능이 급격히 떨어지기 때문에, 좁은 범위의 정수 정렬에 적합하며 범용적으로 사용하기는 어렵다.

 

시간 복잡도

\( O(n + k) \) 로 작동한다. 여기서 n은 엘리먼트의 개수이고, k는 범위를 의미한다. 엘리먼트의 범위가 좁은 경우 빠른 속도를 보여준다.

 

안정 정렬(Stable Sort)

같은 값이라면 정렬 전의 순서가 유지되는 안정 정렬이다. 엘리먼트의 수를 세면서 해당 값의 가장 마지막 위치를 저장한 후, 해당 값의 뒤쪽부터 배치하며 안정성을 유지한다.

 

과정

초기 배열을 [ 9, 5, 4, 7, -2, -2, 0, 1 ]로 정의하고 정렬하는 과정을 살펴본다. 먼저 배열을 순회하며 엘리먼트가 등장하는 횟수를 세어 Counting배열에 저장한다. 이후 Counting 배열의 모든 값을 누적합 한 뒤, 해당 값을 인덱스로 사용하며 원본 값의 정렬을 진행한다.

 

 

먼저 원본 배열을 순회하며 최댓값과 최솟값을 찾아준다. max - min + 1이 count 배열의 크기가 된다.

 

 

-2부터 9까지의 숫자가 존재하기 때문에 count 배열의 길이는 12가 된다. 위 이미지에서 count의 윗단은 대응하는 숫자를, 아랫단은 count 배열의 인덱스를 나타낸다.

 

이제 개수를 세어주기 시작할 것이다. 9의 숫자를 셀 때, 9에서 범위 최솟값인 -2를 뺀 값이 count배열에서 9의 인덱스가 된다. 따라서 count[11]을 1 늘려준다.

 

역시 5에서 -2를 뺀 값인 count[7]을 1 늘려준다. 이 과정을 연속해서 진행하면 count 배열을 모두 채울 수 있다.

 

과정을 생략하고 마지막 엘리먼트까지 채웠을 때 count 배열의 상태는 위와 같다. 이제 -2부터 count에 세어놓은 수만큼 새로운 배열에 순서대로 배치한다면 정렬은 완료된다. count를 순회하면서 새로운 배열에 값을 추가하기만 해도 정렬된 결과를 얻을 수 있겠지만 그렇게 얻은 값은 stable하지 않다. 원본 배열의 값을 그대로 사용하기 위해서 count 배열을 누적합 해줄 것이다. 여기서 O(k)의 시간복잡도가 발생한다.

위와 같은 과정을 거치면 누적합 결과를 대응하는 엘리먼트의 index로 사용할 수 있다. 예를 들어 정렬된 배열에서 9는 8번째 엘리먼트여야 한다. -2는 첫 번째와 두 번째 순서가 된다. 이미지를 통해 다시 살펴보자

 

 

각 인덱스가 해당 값의 마지막 위치를 표시하고 있기 때문에, -2를 예로 들면 1, 2번째 중 2를 가리키고 있기 때문에 원본 배열 순회는 뒤쪽부터 시작한다. merge sort가 왼쪽 값을 먼저 앞쪽에 채우면서 stable을 유지했다면 이번엔 오른쪽 값을 뒤쪽으로 채우면서 stable을 유지할 것이다.

 

원본 배열 마지막값인 1에서 최솟값인 -2를 빼서 1의 인덱스를 찾는다. count[1 - (-2)]의 값은 4이고, 이는 1이 정렬 배열의 4번째 엘리먼트라는 것을 의미한다. 배열은 0-index를 사용하고 있으므로 sorted[4-1]에 1을 채워준다. 이때 사용한 count배열의 값을 함께 -1 해줘야 한다. 1이라는 엘리먼트가 여러 개 있을 수 있으므로 해당작업을 해줘야 다음 엘리먼트가 올바른 위치를 찾아갈 수 있다.

 

 

 

0과 -2를 채우는 과정이다. -2는 원본 배열에서 뒤쪽에 위치하고 있었고 정렬된 배열에서도 같은 값 중 가장 마지막에 위치하게 된다.

 

 

원본에서 가장 앞에 있던 -2는 정렬된 배열에서도 여전히 가장 앞에 있다. 이 과정을 반복하면 

 

위의 결과가 완성된다. 이 과정까지 count할 때와 정렬 배열을 채울 때 총 2번 원본 배열을 순회했고, 누적합 과정에서 count 배열을 1번 순회했다. n이 원본 배열의 길이, k가 정렬 데이터의 범위라고 할 때 순회는 \( 2n+k  \) 번 일어난다. 따라서 시간 복잡도는 \( O(n + k) \) 가 된다.

 

아래는 java 구현 코드다. 범위가 너무 커지지 않도록 1000만으로 제한 조건을 두었다.

package solution.implement_sort;

public class CountingSort {
    private int min;
    private int max;

    // 외부에서 호출되는 메서드
    public int[] sort(int[] arr) {
        if (arr == null || arr.length == 0){
            return arr;
        }
        return countingSort(arr, getCountArray(arr));
    }

    private int[] countingSort(int[] arr, int[] count) {
        // 입력 배열에 있는 각 값의 개수를 센다
        countElements(arr, count);
        // counting 배열 누적합
        prefixSum(count);

        int[] sorted = new int[arr.length];

        // 안정 상태 유지를 위해 뒤부터 순회
        for (int i = arr.length - 1; i >= 0; i--) {

            // 0인덱스이므로 - 1
            sorted[--count[arr[i] - min]] = arr[i];
        }

        return sorted;
    }

    private void countElements(int[] arr, int[] count) {
        for (int number : arr) {
            // arr의 value를 count 배열의 index로 사용한다
            count[number - min] += 1;
        }
    }

    private void prefixSum(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            numbers[i] = numbers[i] + numbers[i - 1];
        }
    }

    private int[] getCountArray(int[] arr) throws IllegalArgumentException {
        findRangeBound(arr);
        // 유효 범위가 아니라면 exception이 발생한다.
        validateRange();

        return new int[max - min + 1];
    }

    private void validateRange() {
        // 찾은 범위로 배열을 생성한다.
        // 범위가 천만을 넘어가면 exception을 발생 시킨다.
        if (max - min >= 10_000_000) {
            throw new IllegalArgumentException("범위 초과");
        }
    }

    private void findRangeBound(int[] arr) {
        // count 배열 생성을 위한 범위가 필요하다.
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        // N번 순회하며 최대값과 최소값을 찾는다
        for (int number : arr) {
            max = Math.max(max, number);
            min = Math.min(min, number);
        }

        // 클래스의 필드 멤버에 저장
        this.max = max;
        this.min = min;
    }
}