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

이번 포스팅에서는 계수 정렬(Counting Sort) 에 대해 알아보겠다. 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬을 공부해 보았다. 이 중 가장 빠른 정렬 알고리즘의 시간 복잡도는 O(N*logN)이었다. 이번에 배울 계수 정렬은 시간 복잡도가 O(N)이다. 하지만 데이터의 범위에 대해 조건이 있는 경우만 아주 빠른 속도를 보여준다.

계수 정렬(Counting Sort)

원소간 비교하지 않고 각 원소가 .몇개 등장하는지 갯수를 세어 정렬하는 방식이다.

모든 원소는 양의 정수이다.

시간 복잡도는 O(n + k)로 퀵 정렬, 병합정렬에 비해 일반적으로 빠르다.

정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나. O(n + k)의 공간 복잡도를 가진다.

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

위와 같은 30개의 데이터를 정렬한다고 하자. 위의 데이터는 1부터 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
0	0	0	0	0

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번째 상태

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번째 상태

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번째 상태

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번째 상태

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

위와 같은 방식으로 해당 크기의 원소를 만나는 경우 숫자를 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

#include<iostream>

using namespace std;

int main(void)
{
	int count[6]; // 정렬할 수의 최댓값 + 1만큼 누적합 배열 할당
	int array[30] = { 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 };

	for(int i = 1; i <= 5; i++) // 갯수를 카운트할 배열 초기화
		count[i] = 0;
	for (int i = 0; i < 30; i++) // 각 크기의 갯수 카운트
		count[array[i]]++;
	for (int i = 1; i <= 5; i++) // 순서대로 갯수만큼 출력
	{
		if(count[i] != 0)
			for (int j = 0; j <= count[i]; j++)
				cout << i << " ";
	}
}

코드도 아주 간결하다. 데이터의 크기가 1부터 5 사이인 점에서 반복 또한 5번만 수행하면 된다. 모든 데이터의 크기 범위를 메모리 상에 표현할 수 있다면 O(N)이라는 압도적인 속도로 정렬을 수행할 수 있다는 것이다. 그러나 Counting Sort는 대부분의 상황에서 엄청난 메모리 낭비를 야기할 수 있다. 예를 들어, 1, 1, 3, 100 의 데이터를 정렬하기 위해서는 누적합 배열의 길이를 101로 잡는 메모리 낭비를 하게 된다. 만약 배열의 최댓값으로 10억이 포함되었다면 엄청난 낭비가 될 것이다. 이러한 문제점 때문에 위와 같이 범위가 특정한 상황에서만 주로 사용이 된다.

참조
https://blog.naver.com/ndb796/221228361368
https://yaboong.github.io/algorithms/2018/03/20/counting-sort/

Algorithm