[Sort]Counting Sort(계수 정렬)

설명

• 비교를 하지 않는 알고리즘
• Stable Sort(안정 정렬)입니다.
• 단 정렬하고자 하는 배열의 최댓값이 작을 때 그리고 원소들 간의 차이가 크지 않을 때만 사용 가능합니다.

예제

앞에서부터 배열을 Scan하면서 원소들의 갯수를 파악해 배열에 저장하면 다음 그림과 같게 됩니다.

이를 바탕으로 배열 A를 정렬하면 아래 그림과 같게 됩니다.

 

그런데 이를 더욱 효율적으로 수행하기 위해 C 배열을 다음과 같이 바꾸어줍니다.

$C'[i] = \sum_{0}^{i}C[i]$

그러면 아래와 같은 결과를 얻을 수 있습니다.

마지막 원소는 원소의 총 갯수가 됨을 알 수 있습니다.

 

이를 이용해 정렬을 하는 방법은 아래와 같습니다.

Stable 정렬을 수행하기 위해 맨 뒤에서부터 원소를 탐색합니다.

첫번째 원소는 8번 index에 있는 3입니다. C'의 3번 값을 보면 7이라고 되어 있습니다.

이 것의 의미는 '7번째 index에 위치시켜라' 입니다.

그러면 아래와 같은 결과를 얻을 수 있습니다.

index 8에 있던 3을 정렬시킬 index B의 7번째의 위치한 것을 확인할 수 있습니다.

그리고 C' 배열에서는 3의 값을 1개 감소시켜줍니다. 

이런식으로 6번째 index까지 진행하면 아래와 같은 결과를 얻게 됩니다.

이렇게 마지막 index부터 처음 index 방향으로 값을 조회해 가면 Stable 하게 정렬을 완성시킬 수 있습니다.

 

Pseudo Code

COUNTING_SORT(A, B, k)
	for i = 0 to k
    	C[i] = 0
  	
    for j = 1 to A.length
    	C[A[j] = C[A[j]] + 1
    # C[i] 는 값이 i인 원소들의 개수를 갖게 됩니다.
    
    for i = 1 to k
    	C[i] = C[i] + C[i - 1]
    # C' 배열을 만드는 과정입니다.
    # C[i] 는 i보다 작거나 같은 원소들의 개수가 됩니다.
    
    for j = A.length downto 1
    	B[C[A[j]] = A[j]
        C[A[j]] = C[A[j]] - 1

 

시간 복잡도

총 시간 복잡도 : $O(k + n)$

→ 이 때 k는 배열의 원소들의 범위

 

만약 $k = O(n)$ 이면 시간 복잡도는 $O(N)$ 이 됩니다.

→ 즉 k 의 값이 작을 때만 사용 가능합니다.