계수 정렬 (Counting Sort)

각 숫자가 몇 번 나오는지 센 다음, 그 개수를 이용해 각 값이 들어갈 자리를 바로 계산하는 정렬입니다.

한눈에 보기

• 계수(Counting) = 개수를 센다는 뜻입니다. 각 숫자가 몇 번 등장했는지 세는 과정이 필요합니다.
• 비유하면, 반 학생들의 키를 정렬할 때 서로 비교하지 않고, 바닥에 140cm, 141cm ... 칸을 그려 두고 각자 자기 키 칸에 서게 한 뒤, 앞 칸부터 차례로 불러내는 것과 같습니다.
• 원소끼리 크기를 비교하지 않는 비교 아닌 정렬(non-comparison sort) 입니다.
• 아래 코드처럼 누적합을 쓰고 뒤에서부터 채우면 안정 정렬입니다.
• 카운트 배열과 결과 배열이 따로 필요하므로 제자리 정렬이 아닙니다.

비교 정렬(Comparison Sort)의 한계

N개 원소를 줄 세우는 방법은 모두 N!가지입니다. 비교 정렬은 "a < b인가?"라는 예/아니오 질문을 반복하므로, 질문 과정을 트리(결정 트리)로 그리면 높이가 h일 때 끝(말단 노드)은 최대 2^h개입니다.

• 모든 경우를 구분하려면 말단 노드가 N! 개 이상이어야 하므로 2^h ≥ N! 을 만족해야 합니다.
• 양쪽에 log를 씌우면 h ≥ log₂(N!) 이고, log₂(N!)은 n log n과 같은 크기(Θ(n log n))입니다.
• h는 최악의 경우 비교 횟수, 즉 비교 정렬의 시간복잡도입니다. 그래서 어떤 비교 정렬도 최악의 경우 Ω(n log n)보다 빠를 수 없습니다.

이 O(n log n)을 줄일 수 있는 방법은 비교를 하지 않는 것입니다. 계수 정렬은 비교 대신 "개수 세기"로 정렬합니다.

동작 과정

1. counting 배열의 크기를 최댓값이 담기도록 잡습니다 (최댓값이 5면 0 ~ 5, 6칸).
2. 배열을 한 번 돌면서 각 값의 칸을 1씩 증가시킵니다.
3. counting 배열을 누적합으로 만듭니다. 이제 counting[v]는 "v 이하인 값의 개수", 즉 v가 들어갈 마지막 자리 + 1입니다.
4. 원래 배열을 뒤에서부터 돌면서, 해당 값의 칸을 1 줄이고 그 번호 자리에 값을 넣습니다.

예시 배열 [2, 5, 3, 0, 2, 3, 0, 3] (최댓값 5):

값	0	1	2	3	4	5
2단계: 등장 횟수	2	0	2	3	0	1
3단계: 누적합	2	2	4	7	7	8

4단계에서 뒤에서부터 채우는 모습입니다.

순서	꺼낸 값 (원래 위치)	넣은 자리	결과 배열
1	3 (7번)	6	[-, -, -, -, -, -, 3, -]
2	0 (6번)	1	[-, 0, -, -, -, -, 3, -]
3	3 (5번)	5	[-, 0, -, -, -, 3, 3, -]
4	2 (4번)	3	[-, 0, -, 2, -, 3, 3, -]
5	0 (3번)	0	[0, 0, -, 2, -, 3, 3, -]
6	3 (2번)	4	[0, 0, -, 2, 3, 3, 3, -]
7	5 (1번)	7	[0, 0, -, 2, 3, 3, 3, 5]
8	2 (0번)	2	[0, 0, 2, 2, 3, 3, 3, 5]

뒤에 있던 3이 더 뒷자리(6번)에 들어가므로, 같은 값끼리 원래 순서가 유지됩니다.

Python 코드

def counting_sort(arr):
    if not arr:
        return []
    # 1. 최댓값까지 담을 수 있는 counting 배열을 만듭니다
    counting = [0] * (max(arr) + 1)
    sorted_arr = [0] * len(arr)

    # 2. 각 숫자가 몇 번 나오는지 셉니다
    for x in arr:
        counting[x] += 1

    # 3. 누적합으로 바꿉니다 → "이 숫자 이하가 몇 개인가"
    for i in range(1, len(counting)):
        counting[i] += counting[i - 1]

    # 4. 뒤에서부터 돌며 자기 자리에 넣습니다 (뒤에서부터라서 안정 정렬)
    for i in range(len(arr) - 1, -1, -1):
        counting[arr[i]] -= 1
        sorted_arr[counting[arr[i]]] = arr[i]

    return sorted_arr


print(counting_sort([5, 4, 3, 2, 1]))
# 출력: [1, 2, 3, 4, 5]
print(counting_sort([3, 1, 4, 1, 5, 9, 2, 6]))
# 출력: [1, 1, 2, 3, 4, 5, 6, 9]

1. 최댓값이 5라면 0 ~ 5를 담도록 6칸을 만듭니다. 이것이 계수 정렬의 약점입니다. counting 배열 크기를 가능한 값의 범위만큼 크게 잡아야 하므로, 값의 범위가 넓으면 비효율적입니다.
2. 배열을 한 번 돌면서 값에 해당하는 칸을 1씩 올립니다.
3. 앞 칸의 값을 계속 더해 누적합으로 만듭니다.
4. 뒤에서부터 돌며 칸 번호를 먼저 1 줄이고, 그 번호 자리에 값을 넣습니다. 같은 값이 여러 개면 뒤에 있던 것이 더 뒷자리에 들어가므로 안정 정렬이 됩니다.

음수가 섞인 경우

위 코드는 값을 그대로 칸 번호로 쓰므로 0 이상의 정수만 정렬할 수 있습니다. 음수가 있으면 최솟값을 0번 칸으로 옮겨서 셉니다.

def counting_sort_with_negative(arr):
    if not arr:
        return []
    # 1. 최솟값을 0번 칸으로 옮겨서 셉니다 (칸 수 = 최댓값 - 최솟값 + 1)
    lo = min(arr)
    counting = [0] * (max(arr) - lo + 1)
    sorted_arr = [0] * len(arr)

    for x in arr:
        counting[x - lo] += 1
    for i in range(1, len(counting)):
        counting[i] += counting[i - 1]
    # 2. 나머지는 앞의 코드와 같고, 칸 번호만 x - lo로 바뀝니다
    for i in range(len(arr) - 1, -1, -1):
        counting[arr[i] - lo] -= 1
        sorted_arr[counting[arr[i] - lo]] = arr[i]
    return sorted_arr


print(counting_sort_with_negative([3, -2, 0, -5, 3, 1]))
# 출력: [-5, -2, 0, 1, 3, 3]

1. 값 x를 x - lo 칸에 셉니다. 최솟값이 -5라면 -5는 0번 칸, 3은 8번 칸입니다. 이렇게 하면 최솟값이 큰 경우(예: 1000 ~ 1010)에도 칸을 11개만 쓰면 됩니다.
2. 누적합과 뒤에서부터 채우기는 그대로이고, 칸 번호를 x - lo로 계산하는 것만 다릅니다.

시간복잡도와 공간복잡도

경우	시간복잡도
최선	O(n + k)
평균	O(n + k)
최악	O(n + k)

• n은 원소 개수, k는 값의 범위(0부터 시작하면 배열에 나오는 최댓값)입니다. 배열을 몇 번 훑는 O(n)과 counting 배열을 훑는 O(k)를 더한 값입니다.
• k가 n보다 크지 않다면 O(n)으로 매우 빠르지만, 값 하나가 매우 크면(예: 원소 3개인데 최댓값 1억) k 때문에 오히려 느려집니다.
• 공간복잡도: 추가 메모리 O(n + k) 입니다. counting 배열 O(k)에 결과 배열 O(n)이 더해집니다.

장점과 단점

• 사용: 정렬하는 숫자가 특정한 좁은 범위 안에 있을 때 사용합니다. (예: 점수 0 ~ 100, 나이, 알파벳) 접미사 배열(Suffix Array)을 만들 때도 계수 정렬(기수 정렬)을 쓰면 O(n log n)에 구할 수 있습니다. 비교 정렬을 쓰면 O(n log² n)입니다.

장점

• 값의 범위 k가 n 정도로 작으면 O(n)에 정렬할 수 있습니다.
• 안정 정렬이라서 기수 정렬의 자릿수별 정렬 단계로 쓰입니다.

단점

• 배열 크기 n과 상관없이, counting 배열의 크기가 값의 범위 k만큼 커집니다. 값의 범위가 넓으면 메모리 낭비가 심합니다.
• 정수처럼 칸 번호로 바꿀 수 있는 값만 정렬할 수 있습니다.

정리

개념	비전공자 버전 요약
계수 정렬	값마다 칸을 만들어 개수를 센 뒤, 칸 순서대로 꺼내기
누적합	"나보다 작거나 같은 게 몇 개인가"로 내 자리를 바로 계산
뒤에서부터 채우기	같은 값끼리 원래 순서를 지키는 요령 (안정 정렬)
약점	값의 범위가 넓으면 칸이 너무 많아져 메모리 낭비