[JAVA] 카운팅 정렬(계수 정렬 : Counting Sort)에 대하여... (feat. 퀵 정렬은 왜 가장 많이 쓸까?)

 

 

오늘은 정렬법 중에 카운팅 정렬에 대해서 다뤄보도록 하겠습니다.

 

카운팅 정렬은 특정한 조건이 만족되지 않으면 잘 쓰지 않습니다.

 

카운팅 정렬이 지녀야 할 조건에 대해서 먼저 나열하자면,

1. 원소가 양의 정수여야 한다. (실수 x)

2. 최댓값이 1,000,000 (100만) 이하

3. 정렬해야할 원소의 개수가 정렬의 범위보다 커야 한다.

 

사실 세가지 조건중에

실수를 정렬할 수 없다는 것 외에는

모두 꼭 만족해야 하는 조건은 아닙니다.

 

하지만 만족하지 않는다면 카운팅 정렬의 이점이 사라지므로,

카운팅 정렬을 쓸 이유가 없어집니다.

 

그럼 카운팅 정렬은 어떻게 하는 것인지 알아보겠습니다.

 

아래와 같은 배열이 있다고 치면,

 

<원본 배열 arr>

인덱스	0	1	2	3	4	5	6	7	8
값	3	1	4	8	9	3	5	7	2

 

 

1. arr 의 범위를 알기 위해 먼저 최댓값을 구합니다. (최댓값 : 9)

 

 

2. 최댓값을 범위로 가지는, 누적합을 담기 위한 배열 countArr 를 생성합니다. (int[] countArr = new int[10])

(그냥 편의상 임의로 정한 이름입니다.)

 

 

3. arr 를 순회하며 각 원소의 값에 해당하는 countArr 의 인덱스의 값을 1 씩 증가시킵니다. (for 문, countArr[arr[i]]++)

(이 부분에서 '센다' 라는 의미의 카운팅 정렬이란 이름이 붙여졌습니다.)

0	1	2	3	4	5	6	7	8	9
0	1	1	2	1	1	0	1	1	1

 

 

4. countArr 를 순회하며 각 인덱스의 값을 누적해서 합해줍니다. (for 문 , countArr[i] += countArr[i + 1])

0	1	2	3	4	5	6	7	8	9
0	1	2	4	5	6	6	7	8	9

 

 

5. arr 과 같은 크기의, 정렬된 값을 담을 배열 sortedArr 를 만듭니다. (int[] sortedArr = new int[9])

 

 

6. arr 의 끝부터 정렬하는데, 각 인덱스의 원소값을 countArr 의 인덱스로 넣고,

그것에서 -1 한 값을 sortedArr 의 인덱스로 설정한 뒤 원본 arr 의 값을 넣어주고,

countArr 인덱스의 값을 1 차감시켜줍니다.

(for문, sortedArr[countArr[arr[i]] - 1] = arr[i], countArr[arr[i] - 1]--) 

0	1	2	3	4	5	6	7	8
1	2	3	3	4	5	7	8	9

 

카운팅 정렬은 이렇게 되면 완성입니다만,

이 부분에서, 저처럼 '왜 끝에서부터 정렬하는지?' 궁금한 분이 계실까봐 설명을 덧붙이자면,

 

사실 카운팅 정렬에서는 각 인덱스에서 원소의 값이 유일하기 때문에 상관없습니다.

 

이 부분은 카운팅 정렬을 응용한 기수 정렬 (Radix Sort) 에서

안정된 (Stable 한) 정렬을 구현하기 위해서 그렇습니다.

안정적이란, 값이 넣어진 위치에서 이동하지 않는 것을 말하는데,

 

기수 정렬은, 숫자 0~9 에 해당하는 10개 크기의 작은 버킷을 만들고,

각 자릿수마다 버킷에 누적하는 형식의 카운팅 정렬을 하고,

자릿수를 증가시키면서 정렬을 구현합니다.

 

근데 기수 정렬에서 앞의 인덱스부터 정렬을 하게 된다면,

각 자릿수는 맞게 정렬되지만,

자릿수가 바뀐 뒤에 다시 정렬하게 되면,

이전 자릿수의 위치가 뒤집어질 수 있습니다.

 

이해를 위해 예를 들자면,

 

<원본 배열>

0	1	2	3	4
15	81	51	71	14

 

<1의 자리가 누적합된 배열>

0	1	2	3	4	5	6	7	8	9
0	3	3	3	4	5	5	5	5	5

 

<1의 자리를 앞에서부터 정렬한 결과 배열>

0	1	2	3	4
71	51	81	14	15

 

<10의 자리가 누적합된 배열>

0	1	2	3	4	5	6	7	8	9
0	2	2	2	2	3	3	4	5	5

 

<1의 자리가 앞에서부터 정렬된 배열을 가지고, 10의 자리를 앞에서부터 정렬한 결과 배열>

0	1	2	3	4
15	14	51	71	81

 

 

보시다시피 15와 14의 위치가 뒤집어져서,

정렬이 올바르게 수행되지 않았습니다.

 

시간이 부족한 관계로 뒤에서부터 올바르게 정렬한 예제는 생략하겠습니다.

 

어쨌든 이런 이유에서 카운팅 정렬도 관습적으로(?) 뒤에서부터 정렬을 합니다!

 

 

 

이만 카운팅 정렬의 설명은 여기에서 마치고...

 

 

---

 

 

그렇다면,

 

카운팅 정렬의 시간복잡도는 O(n + k) 이라

(n은 원소의 개수, k 는 원소의 범위)

많이 쓰기로 유명한 퀵 정렬보다도 나은

시간복잡도 성능을 보이는데

왜 쓰지 않을까요?

 

그 이유는 이렇습니다.

 

1. "누적합을 위한 배열" + "새로 담을 배열" 의 추가 메모리가 필요하다.

2. 정렬할 원소의 크기에 비해 범위가 훨씬 크면, 마찬가지로 메모리 낭비가 심하다. 

 

따라서, 글의 맨~ 위에서 말씀드린 조건이 맞아야만 이 이유들을 피해갈 수 있습니다.

 

그럼 이제 카운팅 정렬은 왜 안쓰는지 알겠는데...

왜 다른 효율적인 정렬법 중에 주로 쓰이는 것이 "퀵 정렬" 일까요?

 

 

 

말씀드린 대로

우리가 여러 알고리즘을 해결하기 위해

주로 쓰이는 정렬법은 퀵 정렬인데,

 

아주 짧게 말하자면, 구현이 간단하고,

대부분의 언어에서 잘 작동되도록 설계된 정렬법이기 때문입니다.

 

퀵 정렬은,

같은 시간복잡도 O(nlogn) 을 가지는 정렬법 중에서도

평균적으로 더 빠른데,

 

그 이유를 설명하자면,

 

 

퀵정렬의 시간복잡도 O(nlogn) 의

logn 은,

pivot 을 기준으로 배열을 분할하면서

재귀적으로 호출하는 횟수가 logn이고,

 

호출된 함수에서

비교연산을 하는 평균적인 횟수가 n 인데,

 

두 가지 로직이 합쳐져야 정렬이 되기 때문에,

곱해서 평균 O(nlogn) 의 시간복잡도를 가집니다.

 

 

합병정렬 (Merge Sort) 의 경우에는,

 

분할 + 병합의 로직을 수행해서 정렬하는데,

마찬가지로 분할, 합병하는 단계가 logn 이고,

병합 과정에서 비교, 이동 연산을 각 단계에서 n번 수행합니다.

 

따라서 두 단계를 곱한 O(nlogn) 의 시간복잡도를 가지므로,

 

시간복잡도 상으로는 두 정렬법이 같은 효율을 가집니다.

 

 

그러나 준비한 아래의 이미지를 보시면,

퀵 정렬 이미지 = 출처 : https://imgur.com/gallery/omL5k

합병 정렬 이미지 = 출처 : https://imgur.com/gallery/omL5k

 

퀵 정렬은 피벗을 기준으로 나누고,

정렬하고, 또 나누고 정렬하는 것을 반복하기 때문에,

상대적으로 위치의 이동이 적습니다.

 

실제 하드웨어 상에서 같은 위치를 반복적으로 참조하게 되면

CPU 가 해당 페이지를 캐시메모리에 올려서 성능을 높이게 되는데,

 

퀵 정렬은 좁은 범위에서 이동하기 때문에,

캐시 메모리의 이점을 누릴 기회가 많습니다.

(이를 캐시 메모리 적중률 (Cache Hit Rate) 이 높다 혹은 지역성 (Locality) 이 높다고 표현합니다.)

 

 

따라서, 이것이 평균적으로 퀵 정렬을 가장 많이 사용하는 이유입니다.

 

마지막으로 카운팅 정렬을 구현한 코드를 보여드리고 끝내겠습니다!

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = new int[8];
        // 원본배열 arr
        for (int i = 0; i < arr.length; i++)
            arr[i] = (int) (Math.random() * 8 + 1);
        // 각 원소에 랜덤한 값이 할당됐고, 양의 정수여야 하기 때문에 +1 을 했습니다.

        int max = findMax(arr);
        // 최댓값을 찾는 간단한 메소드입니다.
        countingSort(arr, arr.length, max);
        System.out.println(Arrays.toString(arr));
        // 카운팅 정렬을 수행하고 출력합니다.
    }

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

    static void countingSort(int[] arr, int size, int max) {
        int[] countArr = new int[max + 1];
        int i = 0;
        // 카운트(개수를 세서 누적)할 배열을 만들고,
        // 자주 호출될 i를 코드 간결성을 위해 생성합니다.

        for (; i < size; i++)
            countArr[arr[i]]++;
        // 카운트 배열의 인덱스에 해당하는 arr 값의 개수를 셉니다.

        for (i = 1; i < max + 1; i++)
            countArr[i] += countArr[i - 1];
        // 만들어진 카운트 배열을 누적합 형식으로 바꿉니다.

        int[] sortedArr = new int[size];
        // 원본 배열의 값에 대입하기 위한 정렬 배열을 생성합니다.

        for (i = size - 1; i >= 0; i--) {
            sortedArr[countArr[arr[i]] - 1] = arr[i];
            countArr[arr[i]]--;
        } // 여기선 상관없지만, 관습상 뒤에서부터 정렬하고,
        // 정렬하고 난 카운트 배열의 인덱스를 1 차감해줍니다.

        for (i = 0; i < size; i++)
            arr[i] = sortedArr[i];
        // 원본 배열에 정렬된 배열을 담아줍니다.
    }
}

 

모자란 글 읽어주셔서 감사합니다!