카테고리 없음

계수 정렬과 기수 정렬: O(N) 성능의 특수 정렬 기법

kguidebook0001 2026. 4. 18. 09:14

일반적으로 우리가 알고 있는 비교 기반 정렬 알고리즘(퀵, 병합, 힙 정렬 등)은 수학적으로 $O(N \log N)$이라는 시간 복잡도의 하한선을 가집니다. 하지만 데이터의 특성을 미리 알고 있다면, 이 한계를 깨부수고 선형 시간인 $O(N)$ 만에 정렬을 끝내는 마법 같은 기법이 존재합니다. 바로 계수 정렬(Counting Sort)과 기수 정렬(Radix Sort)입니다. 본 포스팅에서는 데이터의 값을 비교하지 않고도 순서를 찾아내는 이들의 독특한 매커니즘을 2,500자 이상의 밀도 있는 텍스트로 분석해 보겠습니다.

1. 계수 정렬(Counting Sort): 값의 빈도를 이용한 정렬

계수 정렬은 데이터를 직접 비교하는 대신, 각 데이터가 몇 번 등장했는지 개수(Count)를 세어 정렬하는 방식입니다. 예를 들어 [1, 4, 1, 2, 7]이라는 수열이 있다면, 1이 두 번, 2가 한 번, 4가 한 번 등장했다는 정보를 인덱스에 저장합니다. 이후 누적 합을 이용하여 각 숫자가 들어갈 정확한 위치를 계산해 냄으로써 정렬을 완료합니다. 비교 연산이 아예 발생하지 않기 때문에 데이터의 개수 $N$과 데이터의 최대값 $K$에 대해 $O(N + K)$라는 경이로운 속도를 보여줍니다.

1-1. 계수 정렬의 치명적인 제약 조건

속도는 압도적이지만 사용 조건이 매우 까다롭습니다. 첫째, 데이터의 값이 양의 정수여야 합니다. 인덱스를 사용하기 때문입니다. 둘째, 데이터의 범위($K$)가 너무 크지 않아야 합니다. 만약 정렬할 데이터는 단 2개인데 값이 1과 10억이라면, 10억 칸짜리 배열을 만들어야 하므로 엄청난 메모리 낭비가 발생합니다. 따라서 계수 정렬은 시험 점수 정렬(0~100점)이나 알파벳 빈도수 측정 등 데이터의 범위를 미리 알 수 있고 그 범위가 제한적일 때 최강의 효율을 발휘합니다.

2. 기수 정렬(Radix Sort): 자릿수별로 정렬하는 지혜

계수 정렬의 메모리 낭비 문제를 극복하면서도 $O(N)$의 속도를 유지하고 싶을 때 사용하는 것이 기수 정렬(Radix Sort)입니다. 기수 정렬은 전체 숫자를 한 번에 정렬하는 대신, 1의 자리, 10의 자리, 100의 자리 순서로 각 자릿수별로 정렬을 수행합니다. 이때 각 자릿수 정렬에는 안정성이 보장된 계수 정렬이 사용됩니다. 낮은 자릿수부터 정렬해 나가는 LSD(Least Significant Digit) 방식이 가장 대중적이며, 숫자의 최대 자릿수를 $D$라고 할 때 $O(D \times N)$의 복잡도를 가집니다.

2-1. 비교하지 않는 정렬의 철학

기수 정렬의 가장 큰 특징 역시 데이터 간의 직접적인 크기 비교를 수행하지 않는다는 점입니다. 자릿수별로 마련된 10개의 '버킷(Bucket, 0~9)'에 데이터를 넣고 빼는 과정만으로 정렬이 완성됩니다. 이는 부동 소수점이나 문자열 정렬에도 응용될 수 있으며, 자릿수가 고정된 대규모 정수 데이터를 정렬할 때 다익스트라나 병합 정렬보다 훨씬 빠르게 동작합니다.

3. 어떤 상황에서 특수 정렬을 선택해야 하는가?

계수 정렬과 기수 정렬은 '범용 정렬'이 아닙니다. 이들을 선택하기 전에는 반드시 데이터의 특성을 전수 조사해야 합니다.

  • 계수 정렬 선택 시: 데이터의 개수는 많지만 값의 범위가 좁을 때(예: 수능 성적 처리, 연령대별 통계).
  • 기수 정렬 선택 시: 데이터의 범위는 넓지만 자릿수가 일정할 때(예: 전화번호 정렬, 우편번호 정렬).
  • 피해야 할 때: 데이터가 실수형(Float)이거나 음수가 섞여 있을 때, 혹은 데이터 범위가 개수에 비해 너무 광범위할 때.

# 계수 정렬(Counting Sort) 핵심 로직 (Python)
def counting_sort(arr):
    if not arr: return []
    max_val = max(arr)
    # 1. 빈도 카운팅 배열 생성
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    
    # 2. 결과 배열에 빈도만큼 순차 삽입
    result = []
    for i in range(len(count)):
        for _ in range(count[i]):
            result.append(i)
    return result
[특수 정렬 핵심 요약]
1. 계수 정렬: 값의 빈도를 인덱스로 활용하여 $O(N+K)$ 속도를 내지만, 메모리 효율이 데이터 범위에 의존합니다.
2. 기수 정렬: 자릿수별로 나누어 정렬하여 계수 정렬의 메모리 문제를 보완하고 $O(DN)$ 속도를 유지합니다.
3. 공통점: 비교 연산을 수행하지 않는 '비비교 정렬'이며 특정 조건하에 비교 기반 정렬보다 압도적으로 빠릅니다.