여러 정렬 알고리즘들 중에서 계수 정렬(Counting Sort) 은 다른 정렬 알고리즘들과는 확연히 다른 특징을 가지고 있습니다.
일반적인 정렬 알고리즘이 요소 간의 비교를 기반으로 동작하는 반면, 계수 정렬은 값의 빈도(count) 를 이용해 정렬을 수행합니다. 이로 인해 특정 조건에서는 매우 빠른 성능을 보이지만, 조건에 맞지 않으면 오히려 비효율적일 수 있습니다.
이 글에서 계수 정렬의 특징과 동작 원리, 주의할 점, 그리고 시간복잡도와 공간복잡도까지 차례대로 살펴보겠습니다.
계수 정렬의 특징
계수 정렬은 값의 분포 범위가 좁은 요소들에 대해 강력한 성능을 보여줍니다.
대표적인 특징은 다음과 같습니다.
- 비교 연산을 사용하지 않습니다.
- 값의 범위가 제한적일수록 효율이 극대화됩니다.
- 정렬 속도가 입력 데이터의 개수뿐만 아니라 값의 최대 범위에 영향을 받습니다.
- 안정 정렬(Stable Sort)이 가능합니다.
이러한 특징 때문에 계수 정렬은 시험 점수 정렬, 나이 정렬 등과 같이 정수 값이며 범위가 명확한 데이터에서 자주 활용됩니다.
그렇다면 왜 계수 정렬은 비교를 하지 않고도 정렬이 가능할까요?
이를 이해하려면 계수 정렬의 아이디어부터 살펴볼 필요가 있습니다.
계수 정렬 아이디어
계수 정렬의 핵심 아이디어는 간단합니다.
각 값이 몇 번 등장했는지를 미리 세어 두고,
그 개수만큼 순서대로 출력한다.
예를 들어 입력 배열이 다음과 같다고 가정해봅시다.
- 먼저 입력 배열에서 최대값을 구합니다. (여기서는 3)
- 0부터 최대값까지를 인덱스로 사용하는 계수 배열(등장횟수를 셀 배열)을 생성합니다.
- 입력 배열을 순회하면서
각 값이 등장할 때마다 그 값을 인덱스삼아 찾은 요소의 값을 증가시킵니다. - 계수 배열을 앞에서부터 순회하며
인덱스를 값으로 하고, 요소의 값만큼 결과 배열에 채웁니다.
이 과정에서 수행되는 연산은 덧셈과 배열 인덱스 접근뿐입니다. 요소 간의 비교와 위치 교환 과정이 없습니다.
반면, 퀵 정렬이나 병합 정렬 같은 비교 기반 정렬은 모든 요소의 선후 관계를 비교하며 위치를 재배치해야 합니다.
이 차이점이 계수 정렬의 시간복잡도에 직접적인 영향을 줍니다.
주의점
계수 정렬은 모든 상황에서 좋은 선택은 아닙니다.
정렬해야 할 요소들의 값의 범위가 크다면, 계수 정렬은 급격하게 비효율적이어집니다.
다음과 같은 경우를 예로 들어보겠습니다.
- 값의 범위: 0 ~ 100,000,000
- 입력 배열: [100, 1, 100000000]
이 경우 계수 정렬을 사용하면
길이가 100,000,001인 계수 배열을 생성해야 합니다.
하지만 실제로 정렬할 요소는 단 3개뿐입니다.
대부분의 인덱스는 사용되지 않음에도 불구하고 메모리를 할당하고 순회해야 하는 심각한 낭비가 발생합니다.
따라서 계수 정렬은 다음 조건을 만족할 때 사용하는 것이 적절합니다.
- 값의 범위가 좁을 때
- 데이터의 개수가 많을 때
- 값은 인덱스로 사용할 수 있어야 하니, 데이터가 정수일 때
시간복잡도와 공간복잡도
- 시간복잡도: O(N + K)
(N: 입력 데이터 개수, K: 값의 최대 범위) - 공간복잡도: O(K)
계수 배열의 크기가 값의 범위에 비례
비교 기반 정렬의 하한선인 O(N log N)을 뛰어넘을 수 있다는 점이 계수 정렬의 가장 큰 장점이지만,
그 대가로 더 큰 메모리를 지불해야합니다.
계수 정렬 의사 코드
- 입력 배열의 요소 중 최대값을 구한다
- 최대값 + 1 크기의 계수 배열을 생성한다
(최대값이 3이면 인덱스는 0~3) - 입력 배열을 순회하면서
각 요소의 값을 계수 배열의 인덱스로 삼아 등장 횟수를 증가시킨다 - 결과 배열을 생성한다
- 계수 배열을 앞에서부터 순회하며
인덱스를 값으로 하여 등장 횟수만큼 결과 배열에 채운다
계수 정렬 Java 예시 코드
public static int[] countingSort(int[] arr) {
int max = 0;
for (int num : arr) {
if (num > max) {
max = num;
}
}
int[] count = new int[max + 1];
for (int num : arr) {
count[num]++;
}
int[] result = new int[arr.length];
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
result[index++] = i;
count[i]--;
}
}
return result;
}