빠른 비교

n은 원소 수, k는 값 범위 또는 진법 크기, d는 자릿수입니다.

계수 정렬

계수 정렬은 값을 비교하지 않고, 각 값이 몇 번 나왔는지 셉니다. 값 범위가 작으면 매우 빠릅니다.

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을 더해 인덱스로 바꿔야 합니다.

안정 계수 정렬

객체를 정렬하거나 기수 정렬의 내부 단계로 쓸 때는 같은 값의 상대 순서가 유지되어야 합니다. 이때는 누적 카운트 배열을 만들어 뒤에서부터 배치하는 안정 계수 정렬을 사용합니다.

기수 정렬

기수 정렬은 숫자를 일의 자리, 십의 자리, 백의 자리처럼 자릿수별로 안정 정렬합니다. 각 단계가 stable이어야 이전 자릿수의 순서가 유지됩니다.

170, 45, 75, 90
1의 자리로 정렬
10의 자리로 정렬
100의 자리로 정렬

기수 정렬은 값 비교 대신 자릿수 분류를 반복하므로 특정 조건에서 O(n log n)보다 빠를 수 있습니다. 다만 구현량이 늘고, 음수나 문자열, 큰 범위 처리에서 실수가 생기기 쉽습니다.

선택 기준

주의할 점