븟츠의 계수 정렬(Count Sort)!

계수 정렬(Count Sort)이란?

• 특정한 조건이 부합할때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
• 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 + 가장 큰 데이터와 가장 작은 데이터가 백만정도 이하의 차이일때 효율적인 정렬 알고리즘이다.
• 모든 범위를 담을 수 있는 크기의 리스트를 선언하여 구현한다.
• 데이터의 개수가 N, 데이터 중 최대값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다.

 

예시를 통해 계수 정렬 이해하기

아래의 표와 같은 성적을 가지고 있는 학생들이 있다고 가정하고, 오름차순으로 아래 성적을 정렬한다고 생각해보자. 누가 어떤 성적을 가지고 있는지는 중요하지 않다고 할 때, 계수 정렬을 이용하여 정렬하는 것이 가장 빠른 정렬 방법이다.

75	90	75	80	90	95	100	100	95	90
75	70	85	80	75	80	90	95	100	50

Step 0 : 성적은 "0" 점 부터 "100" 점 까지 정수로 나타내어 질 것이다. 따라서, "0" 부터 "100" 까지의 크기를 갖는 리스트를 선언해주면 된다. 아래와 같이 리스트를 선언해주고 해당 성적이 나온 개수를 리스트에 저장하면 된다. 실제로 리스트는 "0" 부터 "100" 까지 전부 선언되지만, 아래 표는 간략하게 나타낸 것이다.

50	...	...	70	75	80	85	90	95	100
0	0	0	0	0	0	0	0	0	0

Step 1 : 앞의 데이터부터 하나씩 확인하며 해당하는 데이터가 나올때마다 리스트에 +1 씩 해주면 된다. "75" 를 확인하고 +1 을 해주면 리스트에 아래와 같이 저장될 것이다.

50	...	...	70	75	80	85	90	95	100
0	0	0	0	1	0	0	0	0	0

Step 2 : 그 다음 데이터인 "90" 을 확인하고 +1 을 해주면 된다. 이후, 이를 계속해서 반복한다.

50	...	...	70	75	80	85	90	95	100
0	0	0	0	1	0	0	1	0	0

중략

---

그럼 아래와 같이 리스트가 정리될 것이다.

50	...	...	70	75	80	85	90	95	100
1	0	0	1	4	3	1	4	3	3

리스트가 정리되었다면, 리스트의 앞에서부터 확인하며 해당 데이터의 개수 만큼 출력해주면 정렬은 완료된다. 맨 앞에 "50" 이라는 데이터가 "1" 개 있으니, "50" 은 "1" 번 출력해주면 된다. 이를 반복하여, "70" 은 "1" 번, "75" 는 "4" 번 출력해주면 될 것이다. 이를 반복하면 아래와 같이 정리된다.

50	70	75	75	75	75	80	80	80	85
90	90	90	90	95	95	95	100	100	100

 

Python을 이용하여 계수 정렬 구현

# 성적 데이터 입력
arr = [75, 90, 75, 80, 90, 95, 100, 100, 95, 90, 75, 70, 85, 80, 75, 80, 90, 95, 100, 50]

# 데이터의 모든 범위를 포함하는 리스트 선언, 모든 값은 0으로 초기화
count = [0] * (max(arr) + 1)

for i in range(len(arr)):
	count[arr[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 하나씩 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 하나씩 확인
	for j in range(count[i]):
		print(i, end=' ') # 기록된 정보 출력

 

계수 정렬의 시간, 공간 복잡도

데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할때, 계수 정렬의 시간 복잡도와 공간 복잡도는 둘 다 아래와 같다. $$ O(N + K) $$

앞에서부터 하나씩 데이터를 확인해야하고, 리스트에 저장된 값들을 데이터 중 최댓값의 크기만큼 반복하며 출력해야하기 때문이다.

 

계수 정렬의 특징

1. 데이터의 범위만 한정되어 있고, 데이터의 크기가 많이 중복되어 있으면 있을수록 빠르게 동작하는 정렬 알고리즘이다.
2. 데이터의 최댓값과 최솟값의 차이가 크면 클수록 선언해야하는 리스트의 크기가 커지므로 특정 상황에는 비효율적인 정렬 알고리즘이다.
3. 실수형 데이터는 구현하기 힘들며, 정수형 데이터일수록 효율적으로 사용할 수 있다.