계수 정렬

각 값의 등장 횟수를 세어 정렬하는 비교 기반이 아닌 정렬로, 값의 범위(k)가 작을 때 O(n)이 가능합니다.

동작 과정

[3, 1, 4, 1, 5, 2, 3]  (값 범위: 1~5)

1. count 배열 구성:
   index: [0, 1, 2, 3, 4, 5]
   count: [0, 2, 1, 2, 1, 1]  ← 각 값 등장 횟수

2. 누적합:
   count: [0, 2, 3, 5, 6, 7]

3. 뒤에서부터 원본 순회 → 결과 배열 배치:
   결과: [1, 1, 2, 3, 3, 4, 5]

구현

int[] countingSort(int[] arr, int max) {
    int[] count = new int[max + 1];
    for (int x : arr) count[x]++;

    int[] result = new int[arr.length];
    int idx = 0;
    for (int i = 0; i <= max; i++)
        while (count[i]-- > 0) result[idx++] = i;

    return result;
}

복잡도

• 안정 정렬 O (누적합 방식)
• k = 값의 범위, k >> n이면 비효율

언제 쓰나

• 값 범위 k가 n에 비해 작을 때 (예: 점수 0~100, 나이 0~200)
• k가 너무 크면 (예: 값이 최대 10억) 메모리 낭비로 불가

→ 정렬