계수 정렬 (Counting Sort)

구현 코드 예시

def counting_sort(arr, k):
    """0 이상 k 이하의 정수 배열을 정렬한다."""
    count = [0] * (k + 1)
    for v in arr:
        count[v] += 1

    for i in range(1, k + 1):          # 누적합: count[i] = i 이하인 원소 개수
        count[i] += count[i - 1]

    output = [0] * len(arr)
    for v in reversed(arr):            # 뒤에서부터 읽어야 안정 정렬이 된다
        count[v] -= 1
        output[count[v]] = v
    return output


def counting_sort_simple(arr, k):
    """값에 딸린 데이터가 없다면 세고 다시 뱉기만 해도 된다."""
    count = [0] * (k + 1)
    for v in arr:
        count[v] += 1

    result = []
    for value, c in enumerate(count):
        result.extend([value] * c)
    return result

음수가 섞여 있으면 최솟값만큼 밀어서(offset) 인덱스를 0부터 만들면 된다. count[v - min_v] += 1로 세고, 꺼낼 때 min_v를 다시 더한다.

언제 쓰는가

• 값의 범위가 좁을 때: 나이, 점수, 학년처럼 상한이 명확한 데이터.
• 메모리보다 속도가 급할 때: n이 수백만이어도 k가 작으면 한 번의 순회로 끝난다.
• 기수 정렬의 부품으로: 기수 정렬은 자릿수마다 계수 정렬을 돌리는 구조다. 이때 안정성이 필수라서 누적합 방식이 반드시 필요하다.

반대로 실수, 문자열, 범위가 넓은 정수에는 쓸 수 없다. 이럴 땐 그냥 언어의 기본 정렬을 쓰는 편이 낫다.

자주 하는 실수

• 카운트 배열 크기를 k로 잡는다. 값 k 자체를 담아야 하므로 k + 1이어야 한다. 마지막 값에서 인덱스 오류가 난다.
• 입력을 앞에서부터 읽는다. 누적합 방식에서 정방향으로 읽으면 같은 값들의 순서가 뒤집혀 안정성이 깨진다. 기수 정렬의 부품으로 쓰면 결과 자체가 틀린다.
• 음수를 고려하지 않는다. 음수 값이 들어오면 인덱스가 음수가 되어 파이썬에서는 조용히 배열 뒤쪽을 건드린다. 오류도 안 나서 찾기 어렵다.
• k를 확인하지 않고 쓴다. 값 범위가 큰 데이터에 적용하면 메모리 초과가 난다. 문제의 제약 조건을 먼저 본다.

면접에서 이렇게 물어본다

• 계수 정렬이 O(n log n)보다 빠른데도 만능이 아닌 이유는 무엇인가.
• "비교 정렬의 하한이 O(n log n)"이라는 정리와 계수 정렬이 모순되지 않는 이유를 설명해 보라.
• 누적합 단계가 왜 필요한가.
• 입력을 뒤에서부터 읽어야 하는 이유는 무엇인가.
• 음수가 포함된 배열에는 어떻게 적용하겠는가.
• 계수 정렬을 쓰기 적합한 실제 데이터의 예를 들어 보라.