[계수 정렬] 숫자를 세는 방식의 정렬 알고리즘

Dachaes 2025. 5. 8. 14:16

728x90

계수 정렬(Counting Sort)

계수 정렬(Counting Sort)은 값을 직접 비교하지 않고, 등장 횟수를 세는 방식으로 정렬을 수행하는 비비교 정렬 알고리즘입니다. 정수나 정수로 표현 가능한 데이터를 정렬할 때 매우 빠르며, 특히 데이터 값의 범위가 작고, 중복이 많을수록 효율적입니다.

정렬하고자 하는 값들의 개수를 카운트 배열에 저장한 뒤, 각 값을 정렬된 위치로 바로 배치하는 방식이기 때문에 최악의 경우에도 O(n + k)의 시간 복잡도를 가집니다. (k는 값의 최대 범위)
단점은 데이터 값이 음수이거나, 범위가 너무 넓을 경우 메모리 낭비가 발생할 수 있다는 점입니다.

1. 계수 정렬이란?

계수 정렬은 다음의 방식으로 정렬합니다.

입력 배열의 값들을 세어, 값마다 등장 횟수를 저장
누적 합을 이용하여 각 값이 정렬된 배열에서 차지할 위치 결정
출력 배열에 차례로 값 배치

값을 "비교"하지 않고 등장 횟수로 직접 정렬 위치를 결정하는 것이 핵심입니다.

작동 방식

입력 배열의 최댓값/최솟값 확인합니다.
카운트 배열(count[]) 생성 후, 값의 빈도 저장합니다.
누적 합 배열로 정렬 위치 계산합니다.
출력 배열에 차례대로 삽입합니다.

장점

매우 빠름 (비교 없음)
정렬 안정성 있음
자릿수 정렬 기반 알고리즘(기수 정렬)에서 보조로 자주 사용됨

단점

값의 범위가 넓으면 비효율적
음수 데이터는 직접 사용 불가 (보정 필요)
정수형 데이터만 적용 가능

2. 예시

초기 배열 : [4, 2, 2, 8, 3, 3, 1]

count 배열 : [0, 1, 2, 2, 1, 0, 0, 0, 1]
누적 합 : [0, 1, 3, 5, 6, 6, 6, 6, 7]
정렬 결과 : [1, 2, 2, 3, 3, 4, 8]

3. 언어별 구현 예시 (양의 정수 기준)

a. Python

def counting_sort(arr):
    if not arr:
        return arr

    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    return output

b. C++

vector<int> countingSort(const vector<int>& arr) {
    if (arr.empty()) return {};

    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal + 1, 0);
    vector<int> output(arr.size());

    for (int num : arr)
        count[num]++;

    for (int i = 1; i < count.size(); ++i)
        count[i] += count[i - 1];

    for (int i = arr.size() - 1; i >= 0; --i) {
        output[--count[arr[i]]] = arr[i];
    }

    return output;
}

d. Java

int[] countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    int[] output = new int[arr.length];

    for (int num : arr) count[num]++;

    for (int i = 1; i < count.length; i++)
        count[i] += count[i - 1];

    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    return output;
}

d. JavaScript

function countingSort(arr) {
  if (arr.length === 0) return arr;

  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  const output = new Array(arr.length);

  for (const num of arr) count[num]++;
  for (let i = 1; i < count.length; i++) count[i] += count[i - 1];

  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }

  return output;
}

4. 시간 복잡도 분석

케이스	시간 복잡도
최선	O(n + k)
평균	O(n + k)
최악	O(n + k)
공간 복잡도	O(n + k)
정렬 안정성	안정 정렬

n : 입력 배열 길이
k : 값의 범위

5. 마무리

계수 정렬은 정수의 개수를 세어서 직접 위치를 계산해 정렬하는 비교하지 않는 정렬 알고리즘입니다.
정수형, 범위가 작고 중복이 많은 데이터에 매우 효율적입니다.
음수 처리나 범위가 큰 데이터에는 부적합하므로 적용 조건이 제한됩니다.
기수 정렬의 핵심 구성 요소로도 자주 활용됩니다.