컴퓨터공학 300 주제 시리즈의 067번째 글이다. 전체 지도는 여기.

한 줄 요약

키가 작은 범위의 정수라면 비교 대신 “개수를 세어 자리를 계산” 해서 Θ(n + k) 에 정렬할 수 있다(계수 정렬). 키가 크면 자릿수별로 안정한 계수 정렬을 반복한다(기수 정렬).

왜 필요한가

앞 글에서 비교 기반 정렬은 최악에 Ω(n log n) 번 비교가 필요하다고 했다. 이 하한은 “두 원소를 비교하는 것 말고는 키에 대해 아무것도 모른다” 는 가정에서 나온다. 키가 0~255 사이 정수라는 사실을 안다면 가정이 깨지고, 하한도 적용되지 않는다.

시험 점수 100만 개를 정렬한다고 하자. 점수는 0~100 이다. 비교 정렬은 약 2천만 번 비교한다. 계수 정렬은 101칸짜리 표에 개수를 세고 한 번 펼치면 끝난다.

핵심 개념

계수 정렬(counting sort)

키가 0 이상 k 미만 정수라고 하자.

  1. 크기 k 의 배열 cnt 에 각 키의 등장 횟수를 센다. Θ(n).
  2. 누적합을 만든다. 이제 cnt[d] 는 “키가 d 이하인 원소 수” 이고, 키 d 인 원소들이 출력에서 들어갈 구역의 끝 위치를 뜻한다. Θ(k).
  3. 입력을 뒤에서부터 훑으며 cnt[key] 를 하나 줄이고 그 자리에 원소를 놓는다. Θ(n).
입력 키:  3 1 3 2      k = 4
cnt:     [0,1,1,2]     (키 0:0개, 1:1개, 2:1개, 3:2개)
누적:     [0,1,2,4]
뒤에서부터 배치:
  2 → cnt[2]=2→1, out[1]=2
  3 → cnt[3]=4→3, out[3]=3(두 번째 3)
  1 → cnt[1]=1→0, out[0]=1
  3 → cnt[3]=3→2, out[2]=3(첫 번째 3)
출력:     1 2 3 3      같은 3 끼리 원래 순서 유지

뒤에서부터 넣는 이유는 안정성 때문이다. 같은 키의 마지막 원소가 그 구역의 마지막 칸을 차지하므로 원래 순서가 보존된다. 이 안정성이 기수 정렬의 전제 조건이다.

복잡도는 시간 Θ(n + k), 추가 공간 Θ(n + k). k 가 n 에 비해 작을 때(k = O(n)) 선형이다. k 가 2³² 이면 표 자체가 너무 커서 쓸 수 없다.

기수 정렬(radix sort)

32비트 정수처럼 키 범위가 크면 자릿수로 쪼갠다. 가장 낮은 자리부터(LSD) 안정 정렬을 반복한다.

입력:     170  45  75  90 802  24   2  66
1의 자리: 170  90 802   2  24  45  75  66
10의 자리: 802   2  24  45  66 170  75  90
100의 자리:  2  24  45  66  75  90 170 802

왜 낮은 자리부터일까. 100의 자리로 마지막에 정렬할 때 같은 100의 자리 값끼리는(예: 24, 45, 66, 75, 90 모두 0) 직전 단계의 순서, 즉 아래 두 자리 기준 정렬 순서가 안정성 덕분에 그대로 유지된다. 그래서 최종 결과가 전체 키 기준으로 정렬된다. 각 단계가 안정적이지 않으면 이 논리가 깨진다.

복잡도: 자릿수 d, 각 자리 값의 범위 b 라면 Θ(d·(n + b)). 32비트 정수를 8비트씩 4번 처리하면 d = 4, b = 256 이라 사실상 Θ(n) 이다.

자릿수 크기 고르기

자리 폭 단계 수 (32비트) 표 크기 성질
1비트 32 2 단계가 너무 많다
8비트 4 256 표가 캐시에 들어가 흔히 쓰인다
16비트 2 65536 단계는 적지만 표가 크다

MSD 기수 정렬

가장 높은 자리부터 나누는 방식도 있다. 첫 자리로 버킷을 나눈 뒤 각 버킷을 재귀로 정렬한다. 문자열처럼 길이가 제각각인 키에 잘 맞고, 앞자리에서 이미 구분되면 뒷자리를 볼 필요가 없다.

한계

  • 키가 정수나 고정 길이로 쪼갤 수 있는 형태여야 한다. 임의의 비교 함수만 주어진 객체에는 못 쓴다.
  • 음수는 부호 비트를 뒤집는 등 변환이 필요하다. 부동소수점도 비트 표현을 조작하면 가능하지만 주의가 필요하다.
  • 추가 메모리 Θ(n) 이 든다.
  • n 이 작으면 상수 비용 때문에 비교 정렬보다 느리다.

직접 해 보기

안정한 계수 정렬을 만들고, 그것으로 기수 정렬을 조립한다. python3 로 실행해 확인했다.

def counting_sort(a, key, k):
    """key(x) 가 0..k-1 정수. 안정 정렬."""
    cnt = [0] * k
    for x in a:
        cnt[key(x)] += 1
    for i in range(1, k):            # 누적합: cnt[d] = d 이하 키의 개수
        cnt[i] += cnt[i - 1]
    out = [None] * len(a)
    for x in reversed(a):            # 뒤에서부터 → 안정성
        d = key(x)
        cnt[d] -= 1
        out[cnt[d]] = x
    return out

def radix_sort(a, base=10):
    m = max(a)
    exp = 1
    while m // exp > 0:
        a = counting_sort(a, lambda x: (x // exp) % base, base)
        print(f"  자리 {exp:>4}: {a}")
        exp *= base
    return a

data = [170, 45, 75, 90, 802, 24, 2, 66]
print("입력:", data)
print("결과:", radix_sort(data))

# 안정성: 점수로 정렬해도 같은 점수의 이름 순서 유지
people = [("kim", 3), ("lee", 1), ("park", 3), ("choi", 2)]
print(counting_sort(people, key=lambda p: p[1], k=4))

출력:

입력: [170, 45, 75, 90, 802, 24, 2, 66]
  자리    1: [170, 90, 802, 2, 24, 45, 75, 66]
  자리   10: [802, 2, 24, 45, 66, 170, 75, 90]
  자리  100: [2, 24, 45, 66, 75, 90, 170, 802]
결과: [2, 24, 45, 66, 75, 90, 170, 802]
[('lee', 1), ('choi', 2), ('kim', 3), ('park', 3)]

마지막 줄에서 점수 3인 kim 과 park 은 입력 순서대로 나왔다. 실험 삼아 reversed(a) 를 a 로 바꿔 보면 같은 키의 순서가 뒤집히고, 기수 정렬 결과가 틀려지는 것을 확인할 수 있다.

현업에서는

  • 히스토그램과 버킷 집계. HTTP 상태 코드별 개수, 응답 시간 구간별 개수를 세는 일은 계수 정렬의 1단계 그 자체다. Prometheus 히스토그램 같은 버킷 기반 지표도 같은 발상이다. 정렬까지 갈 필요 없이 개수만으로 분위수를 근사할 수 있다.
  • 고정 폭 키. IPv4 주소(32비트), 타임스탬프, 고정 길이 ID 처럼 정수로 볼 수 있는 키를 대량으로 정렬할 때 기수 정렬이 후보가 된다. GPU 정렬 라이브러리들이 기수 정렬을 주로 쓰는 것도 단계마다 하는 일이 단순하고 병렬화가 쉬워서다.
  • 다중 키 정렬. “덜 중요한 키부터 안정 정렬을 반복” 하는 기법은 LSD 기수 정렬과 같은 원리다. Python 공식 정렬 문서가 이 방법을 소개한다.
  • 표준 라이브러리 정렬 대신 쓸 때는 측정부터. 대부분의 언어 런타임 정렬은 비교 정렬이다. 데이터가 작으면 그쪽이 더 빠르다. 기수 정렬은 데이터가 크고 키가 정수일 때 실측으로 이득이 확인될 때 고른다.

확인 문제

  1. 계수 정렬에서 키 범위 k 가 n² 이면 복잡도는? 이때 기수 정렬로 어떻게 개선하는가?
  2. LSD 기수 정렬의 각 단계가 안정 정렬이어야 하는 이유를 한 문장으로 말하라.
  3. 비교 정렬의 Ω(n log n) 하한이 계수 정렬에 적용되지 않는 이유는?
  4. 음수가 섞인 정수 배열을 계수 정렬하려면?

풀이

  1. Θ(n + n²) = Θ(n²) 이다. 키를 n 진법 두 자리(0..n−1 두 개)로 보고 기수 정렬하면 Θ(2(n + n)) = Θ(n).
  2. 높은 자리가 같은 원소끼리는 이전 단계에서 만든 낮은 자리 순서가 그대로 남아야 전체 순서가 맞기 때문이다.
  3. 하한은 원소끼리 비교만으로 정보를 얻는 모델에서 성립한다. 계수 정렬은 키 값을 배열 인덱스로 직접 써서 비교 없이 위치를 계산한다.
  4. 최솟값 m 을 빼서 0 부터 시작하도록 이동한 뒤(key = x − m, k = max − m + 1) 정렬한다.

더 읽을거리 (References)