Counting Sort 계수 정렬

 

Counting Sort는 말 그대로 각 숫자가 몇 번 등장했는지를 세는 정렬입니다.

 

(a) 상황 - 배열 A에서 나온 각 값의 등장 횟수를 배열 C에 담아줍니다.

(b) 상황 - 배열 C에 들어있던 횟수들을 누적합으로 새로 C 배열을 구성합니다.

C = [2, 2, 4, 7, 7, 8] 보면 0이 두 번 2가 두 번 3이 세 번 5가 한 번 등장해서

2+2+3+1 = 8 해서 새로 구성한 누적합 마지막 요소가 8인것입니다. 

(c) 상황 - 이제 배열 A의 마지막 인덱스부터 하나하나 정렬해봅시다.

배열 A의 마지막 인덱스 8의 숫자 3을 누적합 배열 C를 통해 새로 B 배열에 배치하면 3이 들어갈 곳은 7번이네요. 

배치한 뒤에는 배열 C에 있는 3의 누적합을 1 감소합니다.

(d) 상황 - 배열 A의 7번째 숫자는 0이므로 배열 C에서 0의 위치가 2라는걸 확인 후 배열 B의 2번에 0을 배치합니다.

배치한 뒤에는 배열 C에 있는 0의 누적합을 1 감소합니다.

(e) 상황 - 배열 A의 6번째 숫자는 3이므로 배열 C에서 3의 위치가 6라는걸 확인 후 배열 B의 6번에 3을 배치합니다.

배치한 뒤에는 배열 C에 있는 3의 누적합을 1 감소합니다.

이렇게 배치한 결과 (f) 배열 B에는 잘 정렬된 결과를 볼 수 있습니다.

 

---

 

특징

 

계수 정렬은 동일한 값을 가진 요소들의 상대적 순서를 유지합니다.

 

k ≤ n

k는 정렬할 수 있는 최대 키 값, n은 입력 배열의 크기입니다.

만약에 100명의 학생 (배열의 크기)가 있다면 0~100점 사이에서 5개의 키값이 [25,45, 75, 29, 100] 점 이렇게 있다면

k = 5가 되기 때문에 이 조건에 부합합니다.

이 때 k의 값이 항상 n보다 작거나 같다면 계수 정렬은 안정적 정렬(stable sort)입니다.

 

시간 복잡도 분석:
Step 1: Θ(k) - 계수 배열 초기화
Step 2: Θ(n) - 입력 배열 순회하며 계수
Step 3: Θ(k) - 계수 배열의 누적 합 계산
Step 4: Θ(n) - 정렬된 배열 생성
총 시간 복잡도: Θ(n+k)
모든 단계를 합하면 Θ(n+k)가 됩니다.

그렇기 때문에 만약에 이 때 k가 n을 뛰어넘게 된다면 k > n이라면 O(n) 시간 복잡도가 아닙니다.

k가 더 영향이 크기 때문에 O(k)가 됩니다.