계수 정렬은 제한된 범위의 정수 키가 몇 번 나타나는지 세어 정렬하는 방법이다.
원리
입력 크기를 n, 키 범위를 k라 하면 대표적인 구현은 O(n+k) 시간과 계수 배열을 사용한다. 누적 개수를 이용하면 원소를 결과의 위치에 배치할 수 있다.
예시
0부터 100까지의 시험 점수를 정렬할 때 각 점수의 개수를 세면 비교를 반복하지 않고 점수순 결과를 만들 수 있다.
주의할 점
키 범위가 매우 크고 입력은 적다면 계수 배열이 비효율적이다. 키만 다시 출력하는 방법과 부가 정보를 가진 레코드를 안정적으로 재배치하는 방법을 구별한다.