계수 정렬 (Counting Sort)

계수 정렬 (Counting Sort)

각 값의 출현 횟수를 세어 정렬하는 비비교 기반 정렬 알고리즘으로, 정수 범위가 제한적일 때 O(n+k) 시간에 정렬

목적: 선형 시간 정렬, 정수·범위 제한

특징: 비비교 기반, 안정 정렬, 범위(k) 의존, 추가 메모리

동작: ① 카운트 배열(크기 k) 생성 → ② 각 값 출현 횟수 카운트 → ③ 누적합 계산 → ④ 출력 배열에 배치(뒤에서부터, 안정성)

시간 복잡도: O(n + k) - n = 입력 크기, k = 값 범위

공간 복잡도: O(n + k) - 카운트 배열 + 출력 배열

장점: 선형 시간(O(n+k)), 안정 정렬, k 작으면 매우 빠름

단점: 범위(k) 클 때 메모리 낭비, 음수·실수 불가(변환 필요), 추가 메모리

적용사례: 정수 정렬(범위 작음), 나이·점수 정렬, 기수 정렬의 하위 루틴

비교: 계수(O(n+k)/정수) vs 기수(O(d(n+k))/자릿수) vs 비교 정렬(O(n log n))

연관: 기수 정렬, 버킷 정렬, 비비교 정렬, 안정 정렬