계수 정렬(Count Sort)

정의

특정 조건이 부합할 때는 매우 빠른 정렬 알고리즘입니다.

특정 조건이란?
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때에 사용할 수 있습니다.
시간복잡도는 O(N+K)로, K는 데이터 중 최댓값입니다. 따라서 데이터의 크기가 제한되어 있다면 데이터 개수가 많더라도 빠르게 동작합니다.
범위 제한
실수형 데이터인 경우 값이 무한한 범위를 가지므로 사용하기 어렵습니다.
적절한 크기 범위
일반적으로 크기 범위가 1,000,000을 넘지 않을 때(가장 큰 데이터 - 가장 작은 데이터 차이가 백만을 넘지 않을때) 효율적으로 사용할 수 있습니다.
- 왜 크기 범위가 제한되어 있어야 좋을까요?
  모든 범위를 담을 수 있는 크기의 배열이 필요하기 때문
  (예: max - min 차이가 A라면 A+1개의 크기의 배열이 필요함. A+1개의 숫자가 범위에 포함되어 있기 때문)

방법

입력 데이터: [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

먼저 MAX와 MIN의 범위가 모두 담길 수 있도록 배열을 생성합니다.

위 배열을 보면 가장 큰 데이터는 '9', 가장 작은 데이터는 '0'입니다.

그럼 0~9를 모두 포함할 수 있도록 크기가 10인 배열을 선언해야 합니다.

그리고 입력 배열을 돌면서 카운팅을 합니다.

카운트한 배열
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]

소스 코드

# 입력 배열
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 카운팅위한 배열
count = [0] * (max(array) + 1) # 입력이 0 이상이라는 가정하에 최댓값까지 포함해서 카운팅 배열 선언
# 카운팅
for i in range(len(array)):
  count[array[i]] += 1
# 카운팅된 배열 작은 값부터 개수만큼 출력
for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=' ')

복잡도

시간 복잡도

위 소스 코드를 보면, 계수 정렬의 시간복잡도는 O(N+K)입니다. 조건만 맞는다면 기수 정렬(Radix Sort)와 함께 가장 빠른 정렬이라고 할 수 있습니다. 단, 기수 정렬은 계수 정렬에 비해 처리할 수 있는 정수의 크기는 더 크고 좀 더 느립니다. (하지만 소스코드가 더 복잡해서 코딩테스트에서 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 거의 출제되지 않는다고 합니다.)

공간 복잡도

데이터의 범위가 1,000,000,000이라면? 카운팅 배열을 int로 선언한다면, 4byte가 1,000,000,000개 필요합니다
∴ 4GB의 공간이 필요합니다. 따라서 사용할 수 없습니다.
예를 들어 입력 데이터가 [0, 9, 0, 9, 0, 9, ....] 등 0과 9로만 이루어져있다고 합시다. 그러면 0과 9만 카운팅하면 되지만, 배열은 크기가 10으로 선언해야 합니다. 따라서 데이터에 따라 비효율적일 수가 있습니다.

그러므로 항상 쓸 순 없고, 범위가 제한되어 동일한 값을 가지는 데이터가 여러 개 등장할 때 효율적입니다. 따라서 데이터 특성을 파악하기 어렵다면 퀵 정렬(대부분 정렬 라이브러리도 퀵 정렬과 비슷한 식으로 구현)이 가장 유리한 것입니다.

참고

이것이 취업을 위한 코딩테스트다 (나동빈)

Previous기수 정렬(Radix Sort)Next해시 테이블 구현

Last updated 2 years ago