Quick Comparison
계수 정렬은 작은 값 범위의 빈도를 세어 O(n+k)에 정렬하고, 기수 정렬은 자릿수별 안정 정렬을 반복해 O(d(n+k))를 노립니다. 여기서 n은 원소 수, k는 값 범위 또는 진법 크기, d는 자릿수이며, 범위가 크면 비교 정렬이 더 단순할 수 있습니다.
| 정렬 | 전제 | 시간 | 핵심 비용 |
|---|---|---|---|
| 계수 정렬 | 값 범위가 작음 | O(n + k) | 카운트 배열 |
| 기수 정렬 | 자릿수로 나눌 수 있음 | O(d(n + k)) | 자릿수별 안정 정렬 |
| 비교 정렬 | 비교 가능하면 됨 | O(n log n) 하한 | 비교 횟수 |
값 범위 k가 원소 수와 비슷한 크기일 때만 계수 배열이 실용적입니다. sparse한 큰 범위나 음수 처리 비용이 크면 비교 정렬이 더 안전합니다.
계수 정렬
계수 정렬은 값을 비교하지 않고, 각 값이 몇 번 나왔는지 셉니다. 값 범위가 작으면 매우 빠릅니다.
int[] count = new int[maxValue + 1];
foreach (int x in arr)
{
count[x]++;
}
int index = 0;
for (int value = 0; value < count.Length; value++)
{
while (count[value] > 0)
{
arr[index++] = value;
count[value]--;
}
}이 방식은 값이 0 이상이고 최댓값이 작을 때 단순합니다. 음수가 있으면 offset을 더해 인덱스로 바꿔야 합니다.
안정 계수 정렬
객체를 정렬하거나 기수 정렬의 내부 단계로 쓸 때는 같은 값의 상대 순서가 유지되어야 합니다. 이때는 누적 카운트 배열을 만들어 뒤에서부터 배치하는 안정 계수 정렬을 사용합니다.
static int[] StableCountingSort(int[] values, int minValue, int maxValue)
{
int range = checked(maxValue - minValue + 1);
var count = new int[range];
var output = new int[values.Length];
foreach (int value in values) count[value - minValue]++;
for (int i = 1; i < count.Length; i++) count[i] += count[i - 1];
for (int i = values.Length - 1; i >= 0; i--)
{
int value = values[i];
output[--count[value - minValue]] = value;
}
return output;
}minValue와 maxValue를 미리 알아야 하며, maxValue - minValue + 1의 overflow와 배열 메모리를 먼저 확인해야 합니다. 뒤에서부터 배치해야 같은 값의 원래 순서가 보존됩니다.
기수 정렬
기수 정렬은 숫자를 일의 자리, 십의 자리, 백의 자리처럼 자릿수별로 안정 정렬합니다. 각 단계가 stable이어야 이전 자릿수의 순서가 유지됩니다.
170, 45, 75, 90
1의 자리로 정렬
10의 자리로 정렬
100의 자리로 정렬기수 정렬은 값 비교 대신 자릿수 분류를 반복하므로 특정 조건에서 O(n log n)보다 빠를 수 있습니다. 다만 구현량이 늘고, 음수나 문자열, 큰 범위 처리에서 실수가 생기기 쉽습니다.
static int[] RadixSortNonNegative(int[] values)
{
var sorted = (int[])values.Clone();
int maxValue = 0;
foreach (int value in sorted)
{
if (value < 0)
{
throw new ArgumentException("음수는 이 구현의 범위 밖입니다.", nameof(values));
}
maxValue = Math.Max(maxValue, value);
}
var output = new int[values.Length];
for (long place = 1; maxValue / place > 0; place *= 10)
{
var count = new int[10];
foreach (int value in sorted) count[(int)(value / place % 10)]++;
for (int digit = 1; digit < count.Length; digit++) count[digit] += count[digit - 1];
for (int i = sorted.Length - 1; i >= 0; i--)
{
int value = sorted[i];
int digit = (int)(value / place % 10);
output[--count[digit]] = value;
}
(sorted, output) = (output, sorted);
}
return sorted;
}이 구현은 10진수 non-negative int만 처리합니다. 각 pass에서 뒤에서부터 output에 배치해 안정성을 지키며, place를 long으로 두어 가장 높은 자릿수 뒤의 곱셈도 안전하게 처리합니다.
선택 기준
| 상황 | 판단 |
|---|---|
| 값 범위가 작고 정수 | 계수 정렬 |
| 점수, 알파벳 빈도 | 계수 배열 |
| 큰 정수지만 자릿수 제한 | 기수 정렬 |
| 음수와 큰 범위가 섞임 | 표준 정렬이 단순 |
| stable 내부 정렬 필요 | 안정 계수 정렬 |
주의할 점
계수 정렬은 n보다 값 범위 k가 훨씬 크면 오히려 비효율적입니다. 원소가 10개인데 최댓값이 10억이면 카운트 배열을 만들 수 없습니다.
기수 정렬은 자릿수별 정렬이 stable이어야 합니다. 중간 단계가 stable이 아니면 최종 결과가 정렬되지 않을 수 있습니다.
참고 링크
1 sources