앞서 살펴본 모든 알고리즘은 비교할 수 있는 것이라면 어떤 객체든 담을 수 있는 배열을 다루었습니다. 수, 문자열, 쌍, 다른 배열 등 거의 무엇이든 가능합니다.
원소가 어떤 작은 집합에만 속할 수 있는 특수한 경우에는 다른 알고리즘인 계수 정렬(영어: counting sort)을 사용할 수 있습니다.
예를 들어, 모든 수가 자연수이고 $1$부터 $100$까지의 범위에 있다는 것이 보장된다고 합시다. 그러면 다음과 같은 간단한 알고리즘이 있습니다:
- 크기가 $100$인 배열을 만들고, 이 배열의 $k$번째 자리에는 수 $k$가 원래 배열에 몇 번 등장했는지를 저장합시다.
- 원래 배열의 모든 수를 차례로 살펴보면서 배열의 해당 값을 $1$만큼 증가시킵시다.
- 각 수가 몇 번 등장했는지 센 다음에는 이 배열을 차례로 훑으면서 $1$을 $1$이 등장한 횟수만큼 출력하고, $2$를 $2$가 등장한 횟수만큼 출력하는 식으로 계속하면 됩니다.
이러한 알고리즘의 실행 시간은 $O(m + n)$입니다. 여기서 $m$은 가능한 값의 개수이고, $n$은 배열의 원소 개수입니다. 집합에 나타날 수 있는 서로 다른 원소의 개수가 비교적 적다면, 계수 정렬은 가장 최적인 해법 중 하나입니다.
#구현 예시
크기가 $100$인 배열 $c$를 만들고, 원래 배열을 한 번 훑으면서 이 배열을 채웁시다.
그다음 원래 배열에서 다음 수를 기록할 위치를 가리키는 포인터 $k$를 두고, $c$의 셀을 하나씩 감소시킬 때마다 이 포인터를 증가시킵니다.
void count_sort(int *a, int n) {
int c[100] = {0};
for (int i = 0; i < n; i++)
c[a[i]]++;
int k = 0;
for (int i = 0; i < 100; i++)
while (c[i]--)
a[k++] = i;
}