[알고리즘] 카운팅(계수)정렬 : Counting Sort

정렬하는 방법 중 하나인 카운팅 정렬에 대해 알아봅시당

카운팅 정렬(Counting Sort)는 정렬 알고리즘으로 O(n)의 시간복잡도를 갖습니다.

다음 정렬 arr을 정렬해보겠습니다.

int[] arr = {8, 5, 4, 1, 7};

arr

6

0

4

1

0

count 배열을 만들어서 arr 배열의 개수를 세줍니다

index	0	1	2	3	4	5	6
count	2	1	0	0	1	0	1

count 배열을 누적합 배열로 만들어줍니다.

index	0	1	2	3	4	5	6
count	2	3	3	3	4	4	5

이제 result 배열을 만들 차례인데요, arr 배열과 같은 크기의 배열을 만들어줍니다.
여기에 정렬된 arr 배열을 담으면 끝입니다!

index	0	1	2	3	4
result	_	_	_	_	_

첫번째로, arr 배열 맨 앞에 있는 '6'을 result배열 올바른 위치에 담아보겠습니다. (arr[0])

count[6] 은 5입니다. (어떻게 보면 당연한 말이죠? 숫자가 5개니 누적합의 최대값도 5일수밖에 없습니다.)
하나를 제대로된 자리에 넣어줄거니 -1을 하면 5-1 = '4'가 됩니다.
'6'의 위치는 '4'가 되는 것 입니다!

index	0	1	2	3	4	5	6
count	2	3	3	3	4	4	4

index	0	1	2	3	4
result	_	_	_	_	6

다음 숫자인 0을 놓아보겠습니다. (arr[1])
count[0] = 2 이므로 -1을 해주면 2-1 = '1'
result[1]에 해당 숫자를 넣어주면 됩니다.
따라서 result[1] = 0이 됩니다.

index	0	1	2	3	4	5	6
count	1	3	3	3	4	4	4

index	0	1	2	3	4
result	_	0	_	_	6

arr[2] 값인 4를 위치시켜 봅시다.
count[4] = 4 이므로 -1을 해주면 4-1 = '3'
result[3]에 해당 숫자를 넣어주면 됩니다.
따라서 result[3] = 4이 됩니다.

index	0	1	2	3	4	5	6
count	1	3	3	3	3	4	4

index	0	1	2	3	4
result	_	0	_	4	6

 

이하 반복... 🔻

• arr[3] 값인 1을 올바른 자리에 위치시켜주기

count[1] = 3이므로 -1을 해주면 3-1 = '2'

result[2]에 해당 숫자를 넣어주면 됩니다.

따라서 result[2] = 1이 됩니다.

index	0	1	2	3	4	5	6
count	1	3	3	3	3	4	4

index	0	1	2	3	4
result	_	0	1	4	6

 

• arr[4] 값인 0을 올바른 자리에 위치시켜주기

count[0] = 1이므로 -1을 해주면 1-1 = '0'

result[0]에 해당 숫자를 넣어주면 됩니다.

따라서 result[0] = 0이 됩니다.

index	0	1	2	3	4	5	6
count	1	3	3	3	3	4	4

index	0	1	2	3	4
result	0	0	1	4	6

이렇게 해서 완성된 result 결과값 배열은 아래와 같습니다.

index	0	1	2	3	4
result	0	0	1	4	6

순서대로 잘 배열됐죠?
안정성을 위해서 뒤에서부터 배열해주면 됩니다!
arr[4] -> arr[3] -> ... -> arr[0]

---

이를 코드로 표현하면 다음과 같습니다.

public class Main { // 카운트정렬
    public static void main(String[] args) {
        int[] arr = {6, 0, 4, 1, 0};
        int[] count = new int[7];
        int[] result = new int[5];

        // count 배열 arr배열값의 자리에 +1씩 해주기
        for(int i=0; i<arr.length; i++){
            count[arr[i]] ++;
        }

        // count 배열 누적으로 만들기
        for(int i=1; i<count.length; i++){
            count[i] += count[i-1];
        }

        // 안정적으로 나열하기 위해 뒤에서부터 순서대로 놓아준다
        for(int i=arr.length-1; i>=0; i--){
            count[arr[i]] --;
            result[count[arr[i]]] = arr[i];
        }

        // result print
        for(int i=0; i<result.length; i++){
            System.out.println(result[i]);
        }
    }
}

카운팅배열 알고리즘의 시간복잡도는 O(n)으로 매우 빠른 정렬법입니다.
그러나 어떤 상황에서는 엄청난 메모리 낭비를 야기할수 있는데요,
예를 들어 4, 5, 1, 99999, 2 를 정렬하려고 할때를 가정해봅시다.
이런 상황에서는 count배열의 크기를 100000으로 잡아야 하기에 엄청난 메모리 낭비가 됩니다!🙀

카운팅배열을 대표적으로 이용하는 경우는 알파벳의 나열이 될 수 있겠죠?
26개의 알파벳은 count 배열의 크기를 26으로 만들면 되니 효율적으로 카운팅배열을 사용할 수 있습니다.