카운팅 정렬(Counting Sort)는 O(N) 성능을 가지는 정렬 알고리즘입니다. 그리고 구현까지 간단해서 알아두면 좋습니다. 흔히 성능을 위해 많이 사용하는 Cache와 비슷한 성격을 갖고 있습니다. O(N) 성능이라고 하면, 그냥 데이터들을 한 번 읽고 지나가면 정렬이 되는 속도라고 볼 수 있습니다.

일반적으로 많이 쓰는 정렬 알고리즘들인 Quick Sort나 Merge Sort가 O(N log N)임을 생각하면 상당히 훌륭한 편입니다. 하지만, 이런 엄청난 속도임에도 정렬 알고리즘의 대표적인 예시가 되지 못하는 이유는 특수한 환경에서만 쓸 수 있는 알고리즘이기 때문입니다.

일단, 원리를 알아보도록 하겠습니다.

원리

Counting Sort의 원리는 다음과 같습니다.

카운팅하고자 하는 숫자 값중 가장 큰 값 만큼의 배열을 하나 만듭니다. 예를 들어서 정렬하고자 하는 값이

{ 5, 14, 2, 7, 11, 3, 6, 10, 9, 18 }

라고 하면, 이 중에서 가장 큰 값이 18이므로 18만큼의 배열을 하나 만듭니다. 넉넉하게 크기 20짜리 배열을 하나 만들어보겠습니다. 저는 아래 코드에서는 result 라는 배열로 만들었습니다. 그리고 데이터를 처음부터 읽으면서 그 값을 인덱스로 하는 칸에 +1 합니다. 예를 들어, 데이터가 숫자 5인 경우는 result[5]를 +1 해주면 됩니다.

이렇게 모든 데이터를 읽어 들인 후, 그 다음에는 result 배열을 처음부터 읽으면서 그 값이 0보다 큰 경우에만 출력을 해주면 됩니다.

코드로 살펴보겠습니다.

코드

const int MAX = 10;
int data[MAX] = { 5, 14, 2, 7, 11, 3, 6, 10, 9, 18, };
int result[20];

int main(int argc, char**argv) {
  for(int i = 0; i < MAX; i++) {
    int index = data[i];
    result[index]++;
  }

  for(int i = 0; i <= 20; i++) {
    if(result[i] > 0) {
      printf("%d ", i);
    }
  }
  printf("\n");

  return 0;
}

주의점

성능이 O(N)이긴 하지만, 항상 Quick Sort나 Merger Sort 보다 더 좋은 성능이 나오지는 않습니다. 예를 들어, N = 2, 데이터는 {1, 999999} 라는 데이터가 있으면 카운팅 정렬을 쓸 경우 훨씬 더 안 좋은 성능이 나올 것입니다.

하지만, 일반적인 실 생활에서나 알고리즘 대회 등에서는 카운팅 정렬을 사용할 기회가 많이 있습니다. { 1, 3, 2, 3, 2, 1, 3, 2, 1, } 와 같이 최대값이 적은 경우는 아주 효과가 큽니다. 그리고 꼭 자연수일 필요는 없습니다. 음수일 경우 모든 값에 특정 값을 더해서 양수로 만들어서 적용할 수도 있고, 소수일 경우엔 특정 값을 곱해서 정수처럼 만들어서 사용할 수도 있습니다. 구현도 쉽기 때문에 정렬이 필요할 때 제일 먼저 카운팅 정렬을 떠올려보고 적용이 가능한지 판단해보는 것도 좋을 것 같습니다.