Algorithm Guidecomplexity: O(n + k)

계수 정렬 (Counting Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Counting Sort · non-comparison

계수 정렬을 시작합니다. 비교 없이 값의 빈도를 세어 O(n+k)에 정렬하는 비교 제외(non-comparison) 알고리즘입니다.

Logic Node1 / 10

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

02 쉽게 이해하기

For Everyone

🔑비유

각 숫자가 몇 번 나오는지 표로 세어, 그 개수대로 다시 늘어놓는 것.

💡쉽게 말하면

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

비교 없이 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