CHAPTER 6. 정렬 - 계수 정렬

4. 계수 정렬

특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 이다. 모든 데이터가 양의 정수일 때, 데이터의 개수가 N 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(K+N)을 보장한다. 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터 개수가 많더라도 매우 빠르게 동작하며 원리 또한 간단하다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.

 

계수 정렬이 효과적인 경우

• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때
  c.f) 0 이상 100 이하인 성적 데이터를 정렬할 때

계수 정렬을 사용할 수 없는 경우

• 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.
• 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 큰 경우

 

Q. 계수 정렬이 이러한 특징을 가지는 이유?

계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야하기 때문이다. 다시 말해, 가장 큰 데이터와 가장 작은 데이터가 n만큼 차이난다면 n+1개의 데이터가 들어갈 수 있는 리스트를 초기화해야한다. 직접 데이터의 값을 비교하고 위치를 변경하며 정렬하는 방식(비교 기반 정렬 알고리즘)과 달리 계수 정렬은 같은지 다른지를 비교한다.계수 정렬은 일반적으로 별도의 리스트를 선언하고(not in-place sorting) 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

 

동작 예시

* 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 많더라도 빠르게 동작한다.

 

초기 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

 

계수 정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 현재 예시에서는 가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0'이다. 따라서 정렬할 데이터의 범위는 '0'부터 '9'까지 이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 크기가 10인 리스트를 선언한다. 그리고 리스트의 모든 데이터를 0으로 초기화한다. 그다음 데이터를 처음부터 하나씩 확인하면서 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

 

[step 1] 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

 

[step 2] 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

 

[step 3] 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

---------- 중략 ----------

[step 14] 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

 

[step 15] 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

 

결과적으로 위와 같이 리스트에 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있다. 정렬된 결과를 확인하려면 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

c.f) '5' 인덱스의 값은 2이므로 '5'는 2번 등장했다. 그러므로 '5'를 2번 출력하면 된다.

 

정렬 결과 출력

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

→ 출력 결과: 0 0

 

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

→ 출력 결과: 0 0 1 1

 

---------- 중략 ----------

 

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

→ 출력 결과: 0 0 1 1 2 2 3 4 5 5 6 7 8

 

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

→ 최종 출력 결과: 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

 

시간 복잡도

데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할때, 계수 정렬의 시간 복잡도는 O(N + K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 일치하는 인덱스의 값을 1씩 증가시킬 뿐만 아니라 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)와 더불어 가장 빠르다고 볼 수 있다.

 

Big-O Notation: O(N + K)

 

공간 복잡도

계수 정렬의 공간 복잡도는 O(K)이다. 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수도 있는데, 예를 들어 데이터가 0과 999,999 단 2개만 존재하는 경우에도 리스트의 크기가 100만 개가 되도록 선언해야한다. 따라서 항상 사용할 수 있는 방법은 아니며, 값의 중복이 허용될 때 적합하다.

c.f) 시험 성적 - 100점 3명, 99점 2명, 95점 5명 ···

 

Big-O Notation: O(K)

 

반면, 일반적인 경우 평균적으로 퀵 정렬이 빨리 동작하므로 데이터의 특성을 파악하기 어려울 때는 퀵 정렬이 유리하다.

 

다시 한번 정리하면,

• 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하지만 항상 사용할 수는 없다.
• 조건만 만족한다면 데이터의 개수가 많을 때도 효과적으로 사용할 수 있다.

 

다만, 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 인하여 입력되는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서의 데이터 개수는 1,000만 개 미만으로 출제될 것이다.

 

코드

# 계수 정렬 소스코드
# 모든 원소의 값이 0보다 크거나 같은 정수라고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언
count = [0] * (k+1) # 가장 큰 수 k+1만큼, 모든 항목은 0개로 초기화

# 숫자 개수 세기
for i in array:
  count[i] += 1 # 각 데이터에 해당하는 count 리스트의 index의 값을 +1을 해준다.

# 정렬된 결과 출력
for i in range(len(count)):
    print((str(i)+' ') * count[i], end='')