100개 미만의 작은 숫자들을 선형 시간, 즉 O(n) 복잡도로 정렬해야 한다면 카운팅 정렬(Counting Sort) 기법을 사용할 수 있습니다.
카운팅 정렬은 안정 정렬(stable sort) 방식의 알고리즘으로, 키 값이 작은 범위의 정수일 때 매우 효과적입니다. 이 기법은 같은 키 값을 가지는 원소의 개수를 세어(counting) 그 정보를 바탕으로 정렬된 배열을 만듭니다. 다만 키 값들 사이의 차이가 클 경우 카운트 배열의 크기가 커져 공간 복잡도가 증가할 수 있으므로, 값의 범위가 좁고 데이터 수가 많을 때 가장 유리합니다.
카운팅 정렬의 복잡도
시간 복잡도: O(n + r)
공간 복잡도: O(n + r)
여기서 n은 정렬할 데이터의 개수, r은 키 값의 최대 범위를 의미합니다.
입력 − 정렬되지 않은 데이터 목록: 2 5 6 2 3 10 3 6 7 8 출력 − 정렬 후 배열: 2 2 3 3 5 6 6 7 8 10
알고리즘
countingSort(array, size)
입력 − 데이터 배열과 배열의 총 원소 개수
출력 − 정렬된 배열
시작
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] // 누적 빈도 계산
done
for i := size down to 1 do
출력 배열에 해당 숫자 저장
count[i] 감소
done
출력 배열 반환
끝
예제 코드
아래는 C++로 구현한 카운팅 정렬 프로그램입니다. 먼저 배열에서 최댓값을 구한 뒤 그 크기만큼의 카운트 배열을 만들어 각 숫자의 등장 횟수를 세고, 이를 바탕으로 정렬된 결과를 원래 배열에 다시 저장합니다.
#include <iostream>
using namespace std;
void counting_sort(int array[], int n) {
// 1. 배열에서 최댓값 찾기
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
// 2. count 배열 생성 및 초기화
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
// 3. 각 숫자의 등장 횟수 카운트
for (int i = 0; i < n; i++)
count[array[i]]++;
// 4. 카운트 결과를 바탕으로 배열 재구성
int j = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
array[j++] = i;
count[i]--;
}
}
}
int main() {
int array[100], num;
cout << "배열의 크기를 입력하세요 : ";
cin >> num;
cout << "정렬할 " << num << "개의 원소를 입력하세요:" << endl;
for (int i = 0; i < num; i++)
cin >> array[i];
cout << "\n정렬 전 배열 : " << endl;
for (int i = 0; i < num; i++)
cout << array[i] << " ";
counting_sort(array, num);
cout << "\n정렬 후 배열 : " << endl;
for (int i = 0; i < num; i++)
cout << array[i] << " ";
return 0;
}
실행 결과
배열의 크기를 입력하세요 : 8 정렬할 8개의 원소를 입력하세요: 54 89 23 20 18 88 65 31 정렬 전 배열 : 54 89 23 20 18 88 65 31 정렬 후 배열 : 18 20 23 31 54 65 88 89
이처럼 카운팅 정렬은 원소 간 비교 연산 없이 빈도만 세어 정렬하기 때문에, 값의 범위가 작은 정수 데이터를 다룰 때 비교 기반 정렬(O(n log n))보다 더 빠른 성능을 보여줍니다.