카운팅 정렬(Counting Sort, 계수 정렬) 알고리즘

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

카운팅 정렬(Counting Sort, 계수 정렬)이란?

.주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

카운팅 정렬 동작

카운팅(계수) 정렬 수행 과정은 다음의 단계로 이루어진다.

1. 입력 배열의 최댓값, Counting Array 생성

   원소의 누적합을 구하기 위한 Counting Array 생성을 위해 입력 배열의 최댓값이 필요하다. 이후 최댓값 + 1 크기의 Counting Array를 생성하여 입력 배열의 값을 기준으로 조회된 좌표에 입력 배열의 각 원소 개수를 count 한다.

2. 입력 배열 원소 개수의 누적합

   1번 과정에서 Counting Array 생성 및 원소 Count를 마쳤다면 이전 좌표의 원소 개수를 더해나가 누적합 배열로 만들어준다.

3. 입력 배열과 누적합 배열을 이용한 정렬 수행

   입력 배열의 각 원소에 대해 Counting Array에 조회하여 어느 좌표에 들어가야 하는지 체크한 뒤 조회된 원소의 개수를 1 감소시켜 앞의 좌표로 입력받을 수 있게 한다.

위 배열을 정렬해보자. 우선 입력 배열 전체를 스캔해서 최대값 K를 찾고 Counting Array를 생성하면 값 기준으로 조회 시 Counting Array 좌표로의 접근이 가능해진다. 이후 입력 배열의 값을 기준으로 원소 개수를 업데이트 한다.

원소의 개수를 모두 Count했으면 Counting Array를 누적합 배열로 바꿔준다.

이제 입력 배열과 동일 크기의 정렬될 배열을 준비한다.

정렬될 값을 넣기 앞서 누적합 배열의 각 원소의 의미는 다음과 같다.

• $c_1 = 1$ : $b1$에서 $b1$까지 1개 자리 차지
• $c_2 = 2$ : $b_2$에서 $b_3$까지 2개 자리 차지
• $c_3 = 1$ : $b_4$에서 $b_4$까지 1개 자리 차지
• $c_4 = 1$ : $b_5$에서 $b_5$까지 1개 자리 차지
• $c_5 = 1$ : $b_6$에서 $b_6$까지 1개 자리 차지

입력 배열의 값을 차례대로 순회하여 누적합 배열에 조회하면 해당 원소가 어느 좌표로 가야 하는지 알 수 있고 출력 배열에 삽입 후 Counting Array의 값을 1 감소시켜 앞의 좌표에 넣을 수 있게끔 한다.

정렬 과정을 살펴보면 만약 최대값이 주어지지 않은 경우 전체 배열을 탐색해야 하므로 $O(n)$이 소요되고, Counting Array에 개수를 count하는 과정도 $O(n)$이 소요된다. 이후 출력 배열에 값을 입력하여 정렬된 배열을 얻는 과정에도 $O(n)$이 소요된다. 따라서 시간 복잡도는 $O(n)$이 된다. 그러나, 배열의 길이와 상관없이 배열의 최댓값 $K$가 정렬 시간의 변수로 작용하며 배열의 길이가 작은데 $K$가 굉장히 클 경우(ex. [1, 10000]) 정렬 시간은 $K$에 종속된다. 따라서, 일반적으로 카운팅 정렬의 시간복잡도는 $O(n + k)$라고 말한다. 그리고 $K$가 최대한 작아야 유리하므로 입력값의 범위가 작을 때 높은 효율을 보인다.

python 코드

def counting(arr):
    m = max(K)
    C = [0] * (m + 1)
    for a in arr:
        C[a] += 1
    for i in range(1, m + 1):
        C[i] += C[i - 1]
    result = [0] * len(arr)
    for a in arr:
        result[C[a] - 1] = a
        C[a] -= 1
    return result
a = [3, 1, 2, 5, 4, 6]
b = [6, 5, 4, 3, 2, 1]
c = [5, 5, 3, 3, 1, 1]
print(f'counting a:{counting(a)}, b:{counting(b)}, c:{counting(c)}')