계수 정렬 알고리즘 원리, 코드, 시간 복잡도

계수 정렬이 해결하는 문제

요소 쌍을 비교하기만 하는 정렬은 최악의 경우 Ω(n log n)번의 비교가 필요합니다. 계수 정렬은 비교를 전혀 하지 않고 키 자체를 배열 인덱스로 사용해 이 한계를 피합니다. 시험 점수 0~100, 나이, 0~255 범위의 바이트, 별점처럼 키가 작은 정수라면 어떤 비교 정렬보다 빠릅니다.

대가는 키 범위에 비례하는 메모리입니다. 64비트 정수 몇 개가 전체 범위에 흩어져 있다면 계수 배열이 감당할 수 없을 만큼 커져야 합니다.

원리와 예제

값이 0~8 범위(k = 9)에 있는 [4, 2, 2, 8, 3, 3, 1]을 정렬해 봅시다.

1. 각 값을 셉니다. count[v]는 v가 나온 횟수입니다.
2. 누적 합: 각 개수를 그 값 이하인 요소의 수로 바꿉니다. 그러면 count[v]는 v가 들어갈 마지막 위치의 바로 다음 칸을 가리킵니다.
3. 요소 배치: 입력을 오른쪽에서 왼쪽으로 훑으며, 각 값 v에 대해 count[v]를 1 줄이고 그 위치에 v를 씁니다. 오른쪽에서 왼쪽으로 훑으면 같은 값의 원래 순서가 유지됩니다.

따라서 1은 인덱스 0, 2 두 개는 인덱스 1과 2, 3 두 개는 3과 4, 4는 인덱스 5, 8은 인덱스 6에 갑니다. 결과는 [1, 2, 2, 3, 3, 4, 8]입니다.

파이썬 구현

이 안정 버전은 0부터 k - 1 사이의 정수 키를 가진 임의의 객체를 정렬합니다.

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

단순한 정수만 정렬하고 안정성이 필요 없다면, 개수로부터 출력을 다시 만드는 더 간단한 버전을 쓸 수 있습니다. 이 변형은 최솟값만큼 이동시켜 음수도 처리합니다.

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

시간 복잡도와 공간 복잡도

k가 O(n)이면 계수 정렬은 선형입니다. k가 n보다 훨씬 크면, 예를 들어 0~10⁹ 범위의 값 1,000개를 정렬할 때는 계수 배열이 비용을 좌우하므로 비교 정렬이나 기수 정렬이 낫습니다.

계수 정렬과 다른 정렬 비교

여기서 k는 키 범위의 크기, d는 자릿수, b는 기수 정렬이 쓰는 진법(밑)입니다. 누적 합을 사용하고 요소를 오른쪽에서 왼쪽으로 배치하면 계수 정렬은 안정 정렬입니다. 개수로부터 다시 만드는 단순 버전은 단순한 정수에 대해서는 같은 결과를 내지만, 키와 함께 다른 데이터를 옮길 수 없습니다.

변형과 흔한 실수

• 기수 정렬은 자릿수마다 안정 계수 정렬을 한 번씩 실행해, 이 발상을 큰 정수와 고정 길이 문자열로 확장합니다.
• 버킷 정렬은 값을 범위별 버킷에 나눠 담고 각 버킷을 정렬합니다. 값이 균등하게 분포할 때 빠릅니다.
• 정렬 없이 세기만 하기: 히스토그램을 만들거나 최빈값을 찾을 때처럼 개수만 필요한 경우가 많습니다. collections.Counter가 바로 그 일을 합니다.

계수 정렬을 쓰는 경우

키가 요소 수에 비해 작은 범위의 정수일 때 쓰세요. 성적, 나이, 한 달의 날짜, 바이트, 0~255의 색상 채널 값, 작은 열거형 값 등이 그렇습니다. 기수 정렬과 접미사 배열(suffix array) 구성 알고리즘의 내부 단계이기도 합니다. 면접에서는 색상 정렬(sort colors, 값 0, 1, 2), 빈도순 정렬, H-index 같은 문제와, 비교 정렬의 O(n log n) 한계를 어떻게 넘을 수 있는가 하는 고전적인 질문에 등장합니다.