카운팅 정렬(Counting Sort)은 안정 정렬(stable sort) 기법의 하나로, 데이터를 서로 비교하지 않고 각 키 값이 나타난 횟수를 세어 정렬하는 방식입니다. 주로 키가 작은 정수일 때 사용되며, 키 값들 사이의 범위 차이가 크지 않을 때 특히 효과적입니다.
다만 최댓값과 최솟값의 차이가 큰 데이터에 적용하면 그만큼 큰 카운트 배열이 필요해져 공간 복잡도가 증가할 수 있으므로 주의해야 합니다.
카운팅 정렬의 복잡도
- 시간 복잡도: O(n+r) — n은 데이터 개수, r은 키 값의 범위
- 공간 복잡도: O(n+r)
카운팅 정렬의 동작 원리
- 배열에서 최댓값을 구하고, 그 크기(max+1)만큼의 카운트 배열을 생성합니다.
- 입력 배열을 순회하며 각 값의 등장 횟수를 카운트 배열에 기록합니다.
- 카운트 배열을 누적 합으로 변환합니다. 이렇게 하면 각 값이 정렬 결과에서 차지할 위치를 알 수 있습니다.
- 입력 배열을 뒤에서부터 순회하며 출력 배열의 올바른 위치에 값을 배치하고, 해당 카운트를 1씩 감소시킵니다. 뒤에서부터 처리해야 안정성(stability)이 유지됩니다.
입력과 출력
입력: 정렬되지 않은 데이터 목록: 2 5 6 2 3 10 3 6 7 8 출력: 정렬 전 배열: 2 5 6 2 3 10 3 6 7 8 정렬 후 배열: 2 2 3 3 5 6 6 7 8 10
알고리즘
countingSort(array, size)
입력: 정렬할 데이터 배열과 배열 내 원소의 총 개수
출력: 정렬된 배열
Begin
max = 배열에서 최댓값을 구한다.
크기가 [max+1]인 count 배열을 선언한다.
for i := 0 to max do
count[i] = 0 // count 배열의 모든 요소를 0으로 초기화
done
for i := 1 to size do
배열에서 발견된 각 숫자의 count 값을 증가시킨다.
done
for i := 1 to max do
count[i] = count[i] + count[i-1] // 누적 빈도(cumulative frequency)를 구한다.
done
for i := size down to 1 do
출력 배열(output)에 해당 숫자를 저장한다.
count[array[i]] 값을 1 감소시킨다.
done
출력 배열을 반환한다.
End
C++ 구현 예제
#include<iostream>
#include<algorithm>
using namespace std;
void display(int *array, int size) {
for(int i = 1; i<=size; i++)
cout << array[i] << " ";
cout << endl;
}
int getMax(int array[], int size) {
int max = array[1];
for(int i = 2; i<=size; i++) {
if(array[i] > max)
max = array[i];
}
return max; // 배열의 최댓값 반환
}
void countSort(int *array, int size) {
int output[size+1];
int max = getMax(array, size);
int count[max+1]; // count 배열 생성 (max+1개의 요소)
for(int i = 0; i<=max; i++)
count[i] = 0; // count 배열을 0으로 초기화
for(int i = 1; i<=size; i++)
count[array[i]]++; // 각 숫자의 등장 횟수 증가
for(int i = 1; i<=max; i++)
count[i] += count[i-1]; // 누적 빈도 계산
for(int i = size; i>=1; i--) {
output[count[array[i]]] = array[i];
count[array[i]] -= 1; // 동일한 숫자가 있을 경우 count 감소
}
for(int i = 1; i<=size; i++) {
array[i] = output[i]; // 출력 배열을 원본 배열에 저장
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n+1]; // 입력받은 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 1; i<=n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
countSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
※ 위 코드는 컴파일러 확장 기능인 가변 길이 배열(VLA)을 사용하므로, GCC 또는 Clang 환경에서 컴파일하는 것이 좋습니다.
실행 결과
Enter the number of elements: 10 Enter elements: 2 5 6 2 3 10 3 6 7 8 Array before Sorting: 2 5 6 2 3 10 3 6 7 8 Array after Sorting: 2 2 3 3 5 6 6 7 8 10
마치며
카운팅 정렬은 비교 기반 정렬의 이론적 하한선인 O(n log n)을 넘어 O(n+r)의 성능을 낼 수 있는 강력한 기법입니다. 다만 키 값의 범위가 제한적일 때만 유리하므로, 데이터의 분포를 먼저 파악한 후 적용하는 것이 좋습니다. 범위가 넓은 일반적인 데이터에는 퀵 정렬이나 병합 정렬 같은 비교 기반 정렬이 더 적합합니다.