[알고리즘] 계수 정렬 (Counting Sort)

목차

계수 정렬이란?

계수 정렬은 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘이다. 기존의 정렬 알고리즘들은 위치를 바꾸며 정렬을 했는데, 계수 정렬에서는 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요가 없다. 

 

계수 정렬의 큰 특징은 값 비교가 일어나지 않기 때문에 속도가 빠르다는 것이다. 하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간이 필요하다. 그래서, 정렬해야 할 수의 범위가 작을 때에만 유리하다. 이 이유는 예를 보면서 설명하겠다.

 

EX) 0, 100, 2, 10, 10000 오름차순으로 정렬하기

예를 들어서 정렬해야 할 수가 0, 100, 2, 10, 10000이면 고작 5개의 수를 정렬하는데 0부터 10000까지의 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 한다.

 

 

계수 정렬 과정

1. 정렬하고자 하는 배열의 최댓값을 구한다

 

2. 최댓값 크기의 배열에 각 원소를 순회하며 해당 값이 몇 개 인지 저장한다

 

3. 저장된 데이터를 순서대로 출력한다

 

이제 예시를 한번 살펴보도록 하겠다.

 

EX) 1, 3, 2, 4, 3, 2, 5, 3, 1 , 2, 3, 4, 4, 3, 5, 1, 2, 3, 5 ,2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1 정렬하기

 

0. 초기 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
0	0	0	0	0

 

1. 1번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	0	0	0	0

 

2. 2번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	0	1	0	0

 

3. 3번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	1	0	0

 

4. 4번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	1	1	0

 

5. 5번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	2	1	0

 

6. 6번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	2	2	1	0

 

바로 위와 같이 해당 크기의 원소를 만나는 경우 숫자를 1씩 더해가면 된다. 똑같은 방식을 반복하면 결과적으로 다음과 같이 된다.

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
8	6	8	4	4

 

이제 크기 1부터 5까지 해당 숫자만큼 출력하면 정렬은 끝난다. 즉, 1을 8번, 2를 6번, 3을 8번, 4를 4번, 그리고 5를 4번 출력하면 정렬이 이루어진다.

 

정렬 후 : 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 

 

 

계수 정렬 소스 코드

 

static void countingSort() {
    // 정렬할 배열
    int[] array = {1, 3, 2, 4, 3, 2, 5, 3, 1 , 2,
            3, 4, 4, 3, 5, 1, 2, 3, 5 ,2,
            3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
            
    // 크기가 최대값 만큼임 계수 세기용 배열
    int[] count = new int[6];
    
    for (int i = 0; i < array.length - 1; i++) {
        count[array[i]]++;
    }
    
    // 계수만큼 i 출력. 0이면 출력하지 않는다
    for (int i = 1; i <= 5; i++) {
        if (count[i] != 0) {
            for (int j = 1; j <= count[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }
}

 

이전에 봤던 예제를 정렬한다고 해보겠다. 이 코드를 이용해서 출력하면 다음과 같은 결과를 얻는다.

 

 

 

계수 정렬 시간 복잡도

계수 정렬은 배열에 있는 원소들의 개수만 세고 작은 수부터 나열하므로 시간 복잡도는 O(n)이다. 조금 더 구체적으로 보자면 시간 복잡도는 O(n + k)라고 할 수 있다. 이때, k는 배열에 있는 최댓값이다. 그리고 공간 복잡도는 k만큼의 배열을 추가로 만들어야 하기 때문에 O(k)라고 할 수 있다.

 

시간 복잡도 : O(n + k)

 

공간 복잡도 : O(k)

 

 

계수 정렬 장단점

장점

• 데이터의 범위가 작을 때는 O(n)의 시간 복잡도를 가지므로 매우 빠르다

단점

• 데이터의 범위가 크면 만들어야 하는 배열의 크기가 크므로 메모리의 낭비가 심하다