[정렬] 계수 정렬(Counting Sort)

- 원소들의 값이 -O(n) ~ O(n) 범위를 넘지 않는 경우 사용한다. 

- 예를 들어 배열 원소가 {1, 2, 3,..., k}에 속할 때 (k: 상수)

 

계수 정렬 작동 예시

 

다음은 계수 정렬의 알고리즘이다.

countingSort(A, B, n) { // A: 입력배열, B:정렬결과 n: 입력크기 
	for i ← 1 to k // A의 모든 원소는 {1, 2, 3, ..., k} 에 속함
    	C[i] ← 0; 
    for j ← 1 to n 
      	C[A[j]]++; 
    // 이 지점에서 C[i] : 값이 i인 원소의 총 수 
    for i ← 2 to k 
      	C[i] ← C[i] + C[i-1]; 
    // 이 지점에서 C[i] : i 보다 작거나 같은 원소의 총 수 
    for j ← n downto 1 { 
    	B[C[A[j]]] ← A[j]; 
        C[A[j]]--; 
      } 
} 

 

이 정렬의 시간 복잡도는 O(n+k)이다.

데이터가 n일 때, A를 count하며 C에 개수를 업데이트하는 데 O(n)이 걸린다.

C를 가지고 A를 역순으로 훑으며 B를 만들 때도 O(n)이 걸린다.

업데이트 된 C로 직전 요소 값을 현재 요소 값에 더하는 데 k만큼 반복해야 하며 이는 O(k)가 걸린다.

 

따라서, 계수 정렬의 수행 시간은 Θ(n)가 된다. (단, k = O(n)인 경우에 한함)