계수 정렬(Counting Sort) 알고리즘

개요

계수 정렬(Counting Sort)은 정수 데이터가 주어진 범위 내에 존재할 때, 매우 빠르게 정렬할 수 있는 비교 기반이 아닌 정렬 알고리즘이다. 데이터의 빈도수를 카운트 배열에 저장하고, 이를 기반으로 정렬된 결과를 생성하는 방식으로, 평균 시간 복잡도 **O(n + k)**의 매우 빠른 성능을 제공한다. 단, 정수 범위가 제한적일 때만 효율적이다.

---

1. 개념 및 정의

계수 정렬은 다음 절차로 이루어진다:

1. 입력 배열에서 최댓값(K)을 기준으로 길이 K+1짜리 카운트 배열 생성
2. 각 원소의 빈도수를 카운트 배열에 저장
3. 카운트 배열을 누적합으로 변경 (누적합 정렬 시 사용)
4. 누적합을 기반으로 정렬된 결과 배열에 삽입

음수 데이터에는 직접 사용할 수 없고, 변환이 필요하다.

---

2. 동작 원리

단계	설명
1	입력 배열에서 각 값의 등장 횟수를 count 배열에 저장
2	count 배열을 누적하여 위치 정보를 계산
3	입력 값을 하나씩 정렬된 위치에 삽입

기본적으로 정수형 배열 정렬에 적합하며, 비교 연산이 전혀 없다.

---

3. 파이썬 구현 예시

def counting_sort(arr):
    if not arr:
        return []

    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

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

    return result

# 사용 예시
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

이 구현은 가장 기본적인 계수 정렬로, 안정 정렬을 구현하려면 누적합 배열을 이용한 위치 정렬이 필요하다.

---

4. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(n + k) (n: 입력 크기, k: 최댓값)
공간 복잡도	O(k)

k가 n보다 훨씬 작을 때 매우 효율적이며, k가 크면 메모리 낭비가 심해진다.

---

5. 특징 및 장단점

항목	설명
비교 기반 여부	X (값 자체로 위치 계산)
안정 정렬 여부	O (누적합 사용 시 가능)
정수 정렬 전용	범위 내 정수만 가능 (음수 불가)
메모리 사용	많을 수 있음 (O(k))
매우 빠른 성능	정렬 알고리즘 중 최고 수준 (특정 조건 하에서)

---

6. 시각적 예시

입력: [4, 2, 2, 8, 3, 3, 1]

1. count: [0,1,2,2,1,0,0,0,1]
2. 누적합: [0,1,3,5,6,6,6,6,7]
3. 정렬 결과: [1,2,2,3,3,4,8]

---

7. 다른 정렬 알고리즘과 비교

알고리즘	시간 복잡도	공간 복잡도	비교 기반	안정 정렬	특징
계수 정렬	O(n + k)	O(k)	X	O	정수 전용, 매우 빠름
퀵 정렬	O(n log n)	O(log n)	O	X	범용적으로 빠름
병합 정렬	O(n log n)	O(n)	O	O	안정적이지만 메모리 사용 많음
힙 정렬	O(n log n)	O(1)	O	X	정해진 공간 내 일관된 성능

---

8. 활용 사례

분야	활용 예시
시험 점수 정렬	0~100 범위에서 빠른 정렬 가능
통계 데이터 분석	정수 빈도수 기반 정렬/분석
그래프 알고리즘	위상 정렬, 간선 정렬 등에서 활용
대용량 정수 데이터	10^6 이하 정수에 빠른 처리 가능

정수 범위가 작고 고정된 경우에 최고의 성능을 낸다.

---

9. 결론

계수 정렬은 정수 데이터를 빠르게 정렬할 수 있는 효율적인 알고리즘으로, 정렬 성능만 놓고 보면 매우 우수하다. 단, 범위가 큰 데이터에는 부적합하며 메모리 사용이 많아질 수 있다. 비교 연산이 필요 없는 구조 덕분에 특정 문제에서는 최고의 선택이 될 수 있으며, 알고리즘 문제풀이 및 정렬 알고리즘 학습에서도 매우 유용하다.