개념
계수 정렬은 각 숫자의 등장 횟수를 세어 정렬하는 알고리즘이다.
비교 없이 정렬을 수행한다.
O(n + k) 시간 복잡도의 알고리즘으로, 범위가 제한된 정수 정렬에 매우 효율적이다.
정수 배열 A를 입력받으면, 최대값과 같은 길이의 배열 B와 A와 동일한 길이의 배열 C를 선언한다.
배열 B의 인덱스는 A의 값을 의미하며, 각 요소는 해당 값의 등장 횟수를 저장한다.
배열 A를 순회하며 해당 값을 인덱스로 하여 배열 B의 값을 증가시킨다.
이후, 배열 B를 누적 합으로 갱신하여 특정 값보다 작은 값들이 몇 개 있는지 계산한다.
즉, 배열 B의 마지막 값은 배열 A의 길이가 된다.
그 후, 배열 A를 역순으로 순회하며 B의 값을 참조해 배열 C에 A의 값을 올바른 위치에 배치한다.
이 과정을 마치면 비교 연산 없이 정렬이 완료된다.
계수 정렬의 단점은 카운팅을 위한 배열의 길이가 배열 A의 최댓값에 의해 결정된다는 것이다.
숫자의 범위가 클 경우(최댓값이 너무 크거나 분포가 넓을 때) 메모리 사용량이 많아 비효율적이다.
정수형 데이터만 정렬 가능하고, 데이터 간 상대적 크기 정보가 없는 경우(예: 문자열, 실수 등) 적용하기 어렵다.
또한, 동적 데이터(삽입·삭제가 빈번한 경우)에는 적합하지 않다.
