카운팅 정렬(Counting Sort)이란?
카운팅 정렬은 비교 연산 없이 정렬을 수행하는 알고리즘입니다. 배열의 최댓값을 미리 알고 있다면 선형 시간 O(n)과 공간 안에 숫자 배열을 정렬할 수 있어, 데이터 범위가 제한적일 때 매우 효율적인 선택입니다.
동작 원리는 간단합니다. 최댓값을 기준으로 그 크기만큼의 카운트 배열을 만들어 각 인덱스 값이 몇 번 등장했는지 세고, 이후 개수가 0이 아닌 인덱스들을 결과 배열에 순서대로 추출하는 방식입니다.
구현 단계
먼저 반복문 한 번으로 배열의 최댓값을 찾은 뒤, 카운팅 정렬을 적용해 배열을 정렬합니다. 전체 과정은 다음과 같습니다.
- 배열을 순회하여 최댓값을 구합니다.
- 최댓값 + 1 크기의 카운트 배열을 생성하고 모든 요소를 0으로 초기화합니다.
- 원본 배열의 각 값을 인덱스로 삼아 해당 카운트를 증가시킵니다.
- 카운트 배열을 순회하며 개수가 0보다 큰 인덱스를 그 횟수만큼 결과 배열에 채워 넣습니다.
예제 코드
const arr = [4, 3, 1, 2, 3];
const findMaximum = arr =>
arr.reduce((acc, val) => (val > acc ? val : acc), Number.MIN_VALUE);
const countingSort = (arr = []) => {
const max = findMaximum(arr);
const counts = new Array(max + 1);
counts.fill(0);
arr.forEach((value) => counts[value]++);
const res = [];
let resultIndex = 0;
counts.forEach((count, index) => {
for (let i = 0; i < count; i++) {
res[resultIndex] = index;
resultIndex++;
}
});
return res;
};
console.log(countingSort(arr));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 1, 2, 3, 3, 4 ]
참고 사항
카운팅 정렬은 데이터의 최댓값과 최솟값 차이(범위)가 작을 때 가장 효율적입니다. 범위가 지나치게 크면 카운트 배열이 불필요하게 커져 메모리 낭비가 발생할 수 있습니다. 또한 음수가 포함된 배열을 정렬하려면 최솟값만큼 오프셋(offset)을 더해 인덱스를 보정해 주는 추가 처리가 필요합니다.