정의

계수 정렬은 원소들의 등장 횟수를 세어 정렬하는 비비교 기반 알고리즘입니다. 원소들을 비교하지 않고 카운팅만으로 정렬하므로, 값의 범위(k)가 작을 때 O(n+k) 시간에 정렬할 수 있습니다.

핵심 특성

• ✓비교하지 않음 - 원소를 직접 비교하지 않고 카운팅으로 정렬
• ✓O(n+k) 시간 - n은 원소 수, k는 값의 범위
• ✓안정 정렬 - 같은 값의 상대적 순서가 유지됨 (역순 배치 시)
• ✓제약 조건 - 음이 아닌 정수만 가능, k가 크면 비효율적

시간 복잡도