Algorithm Guidecomplexity: O(n + k)

계수 정렬 (Counting Sort)

비교 없이 값의 빈도를 세어 정렬하는 non-comparison 알고리즘입니다. 값의 범위 k가 제한적일 때 O(n+k)의 선형 시간에 안정적(stable)으로 정렬할 수 있습니다.

01계수 정렬 (Counting Sort)

알고리즘 작동 원리 탐색

계수 정렬을 시작합니다. 값끼리 비교하지 않고 각 값이 몇 번 나왔는지만 세어 O(n+k)에 정렬합니다.

1단계 · 세기. 배열을 한 번 훑으며 값마다 몇 번 나왔는지 표에 적습니다.

세기가 끝났습니다. 20·30·40은 두 번씩, 60·70은 한 번씩 — 여덟 개가 모두 기록됐습니다.

2단계 · 자리 정하기. 앞 값의 개수를 차례로 더해 나가면, 각 값이 끝날 자리가 정해집니다.

20은 2번까지, 30은 4번까지, 40은 6번까지 — 이렇게 각 값이 차지할 마지막 자리가 확정됩니다.

3단계 · 자리에 넣기. 원본을 뒤에서부터 훑어 각 값을 제 자리에 놓고, 그 자리를 하나 앞으로 당깁니다.

뒤에서부터 30·40·60을 각자 정해진 자리에 옮겨 놓습니다.

20·30·70이 자리를 잡습니다. 같은 값이라도 원래 뒤에 있던 것이 뒤에 남습니다.

남은 20과 40까지 옮기면 배치가 끝납니다.

정렬 완료 · 20 20 30 30 40 40 60 70. 한 번도 값을 비교하지 않고, 같은 값의 원래 순서도 지켰습니다.

Live Python

1def counting_sort(arr):

# k: max+1 = 71

2 k = max(arr) + 1

3 count = [0] * k

4 for v in arr:

5 count[v] += 1

7 for i in range(1, k):

8 count[i] += count[i - 1]

10 output = [0] * len(arr)

11 for i in range(len(arr) - 1, -1, -1):

12 output[count[arr[i]] - 1] = arr[i]

13 count[arr[i]] -= 1

14 return output

1 / 10

02 쉽게 이해하기

For Everyone

🔑핵심 동작

값마다 몇 번 나왔는지 세어 누적하고, 그 수를 자리로 삼아 늘어놓습니다. 비교하지 않으므로 값의 범위가 좁을 때 O(n) 입니다.

💡쉽게 말하면

값의 출현 횟수를 세어 누적합으로 위치를 정합니다.

비교 없이 O(n+k)로 빠르지만, 값의 범위가 좁아야 해요.

📍어디에 쓰나

–정수·좁은 범위 데이터
–기수 정렬의 내부 단계

03 파이썬 구현 코드

계수 정렬 (Counting Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def counting_sort(arr):
    k = max(arr) + 1
    count = [0] * k
    for v in arr:
        count[v] += 1
    
    for i in range(1, k):
        count[i] += count[i - 1]
    
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output