계수 정렬(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으로 선언해야 합니다. 따라서 데이터에 따라 비효율적일 수가 있습니다.

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

참고

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

• https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html