Counting Sort (계수 정렬)

Counting Sort(계수 정렬)에서 주목할 만한 점은, 이전까지 살펴봤던 다른 정렬 알고리즘들은 특정한 data type에 대한 가정을 따로 세우지 않았다. 하지만 지금 살펴 볼 Counting Sort는 정렬할 data의 type에 대한 가정을 세우고 시작한다. 무슨 말일까? 먼저 Counting Sort가 어떻게 동작하는지 몇 가지 사항을 간단히 살펴보자.

• 정렬할 data의 type에 대한 가정을 세운다.
• 값들 끼리의 비교가 없다. 정렬이 끝날 때까지, 비교는 한 번도 이루어지지 않는다.
  — 대부분의 정렬 알고리즘은 요소 사이의 비교를 필요로 하고(comparison-based), O(NlogN) 이상의 성능을 기대할 수 없다. Counting Sort는 비교 대신 추가적인 배열을 이용하여, 시간복잡도를 O(N)까지 향상시킬 수 있다.
• 배열에서 특정 값이 몇 번 나타나는지 count한다.
• 값들은 음수가 아니어야 하고(non-negative), discrete 해야 한다(부동소수점 안됨). String에 적용할 수 없다.
• 값들은 특정한 범위 내에만 있어야 한다. 예를 들어 1 ~ 100,000 같은 너무 큰 범위는 Counting Sort를 적용하기에 부적절하다.

다음과 같은 배열이 있다. input array라고 하자.

2

5

9

8

2

8

7

10

4

3

정렬은 다음의 과정을 거친다.

1. input array는 1부터 10까지의 값을 가진다고 가정한다.
2. 즉 가능한 값은 10개이다. 따라서 길이가 10인 counting array를 생성한다. (가능한 값의 범위가 10개라는 것이지, 꼭 요소의 개수가 10개여야 한다는 말은 아니다!)
3. 왼쪽에서 오른쪽 방향으로 input array를 탐색한다.
4. counting array는 input array에 각각의 값이 몇개 있는지, 즉 개수를 저장하는 용도로 사용한다.
5. counting array의 개수를 이용해서, input array에 값을 정렬된 순서로 할당한다. (writing back)

위에서 살펴보았듯이 input array(inputArr[])는 다음과 같이 생겼다.

2

5

9

8

2

8

7

10

4

3

값들의 개수를 저장할 counting array는 일단 다음과 같다.

0

0

0

0

0

0

0

0

0

0

값들의 개수를 아직 저장하지 않았으니, 전부 0이라고 표시했다. 이제 input array를 왼쪽부터 하나하나 진행하면서, 값이 나올 때마다 counting array의 해당 위치에 있는 값을 +1 시켜주면 된다.

예를 들어, inputArr[0]은 2다. 그럼 2의 개수를 하나 증가시켜야 하므로, counting array의 2번째 위치에 1을 증가시킨다.

0

1

0

0

0

0

0

0

0

0

이 때 주의할 것은, 애초에 input array 값들의 범위를 1부터 10까지라고 가정했기 때문에, "2번째 위치"라는 것은 그 범위(1부터 10까지) 내에서의 "2번째 위치"를 의미한다. 즉 배열의 첫 인덱스가 0이니 countingArr[2]라고 혼동하면 안된다. 

다음, inputArr[1]은 5다. 5의 개수를 다음과 같이 하나 증가시킨다.

0

1

0

0

1

0

0

0

0

0

같은 방식으로 계속 진행하다 보면, input array의 각 값들의 개수가 counting array에 저장된다. 값의 범위가 1부터 10까지인 input array에 대해, 완성된 counting array의 모습은 다음과 같다.

0	2	1	1	1	0	1	2	1	1
1은 0개	2는 2개	3은 1개	4는 1개	5는 1개	6는 0개	...	...	...	9는 1개

이제 input array 값들이 몇 개 씩 존재하는지 알아냈다. 마지막으로 이것들을 다시 원래의 input array에 "writing back"하는(덮어쓰는) 과정만 남았다. 1은 없으니 스킵하고, 2는 2개 있으니 앞에서부터 2를 2개 넣고, 3은 1개 넣고, ... 와 같이 쭉 진행한다.

2

2

3

4

5

7

8

8

9

10

정렬이 완료되었다! 전체 과정을 세단계로 다시 정리해보면 다음과 같다.

<input array>

2

5

9

8

2

8

7

10

4

3

<counting array>

0

2

1

1

1

0

1

2

1

1

<sorted input array>

2

2

3

4

5

7

8

8

9

10

Counting Sort의 주요 특성을 정리해보자.

• in-place(제자리 정렬)가 아니다. 보다시피 counting array를 위한 추가 공간이 필요하다.
• 시간 복잡도는 O(N)이다. data에 몇가지 가정을 세우고 시작하기 때문에 가능한 결과다.
• input array의 요소의 개수와 값들의 범위가 거의 같을 때 쓰면 유용하다. 그렇지 않은 경우를 극단적으로 예를 들면, input array의 요소의 개수는 10개인데, 값의 범위는 1부터 10000까지라면, 10개 값들의 정렬을 위해 길이가 자그마치 10000인 counting array를 추가로 만들어야 한다. 배보다 배꼽이 더 크니 이럴 때는 Counting Sort를 쓰면 안된다.
• unstable(불안정적)하다. stable하게 하려면 linked-list를 활용해야 한다.

Counting Sort의 개념을 공부했으니, 직접 코드로 구현해보자.

public class Main {

    public static void main(String[] args) {
        int[] intArray = { 2, 5, 9, 8, 2, 8, 7, 10, 4, 3 };

        // Range: from 1 to 10
        countingSort(intArray, 1, 10);

        for (int i = 0; i < intArray.length; i++) {
            System.out.print(intArray[i] + " ");
        }
    }

    public static void countingSort(int[] input, int min, int max) {

        // 숫자의 범위만큼 countArray를 생성
        int[] countArray = new int[(max - min) + 1];

        // Counting phase
        for (int i = 0; i < input.length; i++) {
            countArray[input[i] - min]++;
        }

        // Writing back
        int j = 0;
        for (int i = min; i <= max; i++) {
            while (countArray[i - min] > 0) {
                input[j++] = i;
                countArray[i - min]--;
            }
        }

    }
}