[Algorithms] Counting Sort | 계수 정렬

Counting Sort

계수 정렬

- 정렬하고자 하는 원소들의 값이 \(O(n)\)을 넘지 않는 경우에 사용할 수 있는 알고리즘이다.
(즉, 모든 입력값들이 입력의 개수를 넘지 않아야 한다.)
- Time Complexity = \(\Theta(n)\)

---

Mechanism (메커니즘)

- 입력 배열 \(\texttt{A[1...n]}\)의 원소들을 차례대로 살펴보면서 \(1\)부터 \(k\)까지의 자연수가 각각 몇 번 나타나는지를 Counting한다.
- 입력값들의 입력 빈도를 Counting함으로써 \(\texttt{A[]}\)의 각 원소가 몇 번째에 위치하는지를 계산할 수 있게 된다.

---

Pseudo Code (의사 코드)

countingSort(A[], B[], n) {
// 입력 배열 A[1...n]의 정렬 결과를 B[1...n]에 저장한다.

    for i ← 1 to 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]]--;
    }
}

---

Performance Evaluation (알고리즘 성능 평가)

- 입력 배열을 처음부터 끝까지 순회하므로 \(\texttt{countingSort}\)에 소요되는 시간은 \(\Theta(n)\) 이다.

- 계수 정렬은 입력값들 모두 크지 않은 경우, 선형 시간내에 정렬하기 위해 사용하는 알고리즘이다.
(원소들이 모두 \(-k\)와 \(k\) 사이의 정수이거나, \(k = O(n)\)인 경우에도 계수 정렬을 통해 선형 시간내에 정렬을 완료할 수 있다.
- 단, 여기서 입력값들이 \(O(n)\)을 초과하면 수행 시간은 \(\Theta(k)\)가 되어 병합, 퀵, 힙 정렬보다 뒤쳐지게 된다.