Counting Sort(계수 정렬)

이 글은 인프런의 영리한 알고리즘을 위한 프로그래밍 강좌를 듣고 정리한 내용입니다.

Counting Sort(계수 정렬)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘

- n개의 정수를 정렬하라. 단 모든 정수는 0에서 k 사이의 정수이다.

- 예 : n 명의 학생들의 시험 점수를 정렬하라. 단, 모든 점수는 100 이하의 양의 정수이다.

의사코드

Counting-Sort(A, B, k) {
for i <- 0 to k
do C[i] <- 0
for j <- 1 to length[A]
do C[A[j]] <- C[A[j]] + 1 
// C[i] now contains the number of elements equals to i.
for i <- 1 to k
do C[i] <- C[i] + C[i-1]
// C[i] now contains the number of elements less than or equal to i
for j <- length[A] down to 1
do B[C[A[j]]] <- A[j]
C[A[j]] <- C[A[j]] - 1
}

시간복잡도

- Θ(n+k), 또는 Θ(n) if k=O(n)

- k가 클 경우 비실용적, 단점 : k값의 크기에 큰 영향을 받으므로 공간 효율성은 떨어진다.

- Stable 정렬 알고리즘

입력에 동일한 값이 있을때 입력에 먼저 나오는 값이 출력에서도 먼저 나온다.

Counting Sort 는 Stable 하다.

소스 코드(Java)