이 노트는 정렬 키를 비교하는 대신 키의 표현을 버킷 주소로 바꾸어 분배하는 사고법에서 출발합니다. 먼저 안정 분배가 동점의 순서를 보존하는 이유를 잡고, 그 위에 자리 방향·부호·문자열 종료 규칙을 얹어야 기수 정렬의 정확성과 비용을 함께 설명할 수 있습니다.
비교 정렬과 키 구조 기반 분배
원소가 백만 개이고 키가 0~100 사이 정수라면 각 값이 몇 번 나왔는지 세고 순서대로 출력할 수 있습니다. 두 키를 비교해 순서를 알아내는 대신 값 범위를 직접 주소로 사용하므로 비교 정렬의 일반적인 O(n log n) 하한을 그대로 적용하지 않습니다.
하지만 키가 수십억 범위에 흩어진 백 개 원소라면 카운터 배열이 낭비됩니다. 계수 정렬의 비용은 원소 수 n뿐 아니라 값 범위 R에도 달려 있습니다. 기수 정렬은 전체 값 범위 대신 키를 여러 자리로 나누어 이 분배를 반복합니다.
선택의 첫 질문은 “키를 몇 개의 작은 주소로 안정적으로 분해할 수 있는가”입니다. 값 범위가 작으면 계수 정렬이 단순하고, 고정 폭 정수나 바이트 키면 기수 정렬을 검토할 수 있지만, 비교 비용보다 레코드 이동·캐시·추가 버퍼가 더 큰지 확인해야 합니다.
안정적인 계수 분배 설계
정렬할 레코드가 [2a,1b,2c,0d]라고 해 보겠습니다. 숫자는 정렬 키이고, 문자는 레코드를 구별하는 이름입니다. 원하는 결과는 [0d,1b,2a,2c]입니다. 같은 키를 가진 a와 c는 입력에서의 순서를 유지합니다. 이것을 안정적인 정렬이라고 합니다.
먼저 키별 개수를 세면 [1,1,2]입니다. 이를 누적한 [1,2,4]는 결과 배열에서 각 키가 차지할 구간의 끝을 알려 줍니다. 예를 들어 키 2의 구간은 인덱스 2와 3이고, 그 다음 위치인 4가 누적값입니다.
이제 입력을 뒤에서부터 읽습니다. 먼저 만난 2c를 키 2 구간의 마지막 칸에 놓고, 나중에 만난 2a를 그 앞에 놓습니다. 입력을 거꾸로 읽으면서 각 구간도 뒤에서부터 채우므로, 결과에서는 a가 c보다 앞에 남습니다.
| 단계 | 카운터 또는 결과 | 뜻 |
|---|---|---|
| 빈도 | [1,1,2] | 키 0·1·2의 개수 |
| 누적 끝 | [1,2,4] | 각 키 구간의 배타적 끝 |
| 뒤에서 d | out[0]=0d | 끝 위치를 먼저 1 감소 |
| c, b, a | [0d,1b,2a,2c] | 동점의 원래 순서 보존 |
stableCount(records, digit, R):
count[0..R-1] = 0
for record in records: count[digit(record)] += 1
for k = 1 .. R-1: count[k] += count[k-1]
out = new array(length(records))
for record in reverse(records):
k = digit(record)
count[k] -= 1
out[count[k]] = record
return out
digit는 [0,R)의 정수여야 합니다. 시간 O(n+R), 일반적인 안정 분배의 공간 O(n+R)입니다. 단순 값의 빈도만 출력하는 것과 레코드의 동점 순서를 보존하는 것은 다른 요구입니다.
LSD의 낮은 자리 순서와 안정 분배
두 자리 십진수 [21,12,11,22]를 정렬해 보겠습니다. LSD 방식은 낮은 자리부터 처리하므로 일의 자리로 먼저 나눕니다. 일의 자리가 1인 21과 11, 2인 12와 22가 모여 [21,11,12,22]가 됩니다.
그다음 십의 자리로 나누면 [11,12,21,22]입니다. 여기서 십의 자리가 같은 11과 12의 순서는 앞 단계가 만들어 놓았습니다. 두 번째 분배가 안정적이어서 그 순서가 유지된 것입니다. 만약 같은 십의 자리 안에서 순서를 뒤집었다면 12가 11보다 앞에 올 수도 있습니다.
따라서 ‘낮은 자리부터 정렬한다’만 기억하면 부족합니다. 다음 자리로 분배할 때 이전 단계가 만든 동점 내부의 순서를 보존해야 한다는 것이 LSD 기수 정렬의 핵심입니다.
그림을 글로 읽기
- 21 · 12 · 11 · 22
- 21 · 11 · 12 · 22: 일의 자리 1,1,2,2
- 11 · 12 · 21 · 22: 십의 자리 1,1,2,2
- 21 · 12 · 11 · 22 → 21 · 11 · 12 · 22: 일의 자리 안정 분배
- 21 · 11 · 12 · 22 → 11 · 12 · 21 · 22: 십의 자리 안정 분배
d개 자리, 자리당 R개 버킷이면 O(d(n+R)) 시간입니다. 버킷을 256개에서 더 크게 하면 필요한 단계가 줄 수 있지만 카운터 초기화·캐시·분배 비용이 늘어납니다. 키가 고정 32비트여도 단계마다 큰 레코드 전체를 이동시키면 메모리 대역폭이 지배할 수 있습니다.
음수 키와 unsigned 순서 변환
고정 폭 w비트의 2의 보수 비트를 그대로 unsigned로 읽으면 음수들이 큰 값 영역에 모입니다. 표의 8비트 예에서 -128은 10000000이라 unsigned 128이지만 부호 비트를 뒤집으면 0이 되고, -1은 255에서 127로 내려옵니다. 반대로 0은 128, 127은 255가 되므로 부호 비트를 XOR한 값의 unsigned 순서가 -128, …, -1, 0, …, 127의 signed 순서를 그대로 따릅니다.
| signed 8비트 값 | 비트 패턴 | 부호 비트 XOR 후 unsigned |
|---|---|---|
| -128 | 10000000 | 0 |
| -1 | 11111111 | 127 |
| 0 | 00000000 | 128 |
| 127 | 01111111 | 255 |
실제 코드에서는 부호 있는 overflow를 일으키는 산술 보정보다 언어가 보장하는 unsigned 변환·비트 연산을 사용합니다. LSD는 최하위 의미상의 자리부터 처리하므로 메모리의 첫 바이트부터 읽는 것이 항상 맞지는 않습니다. 엔디언과 자리 추출을 분리하고 마스크·시프트로 정의하는 편이 명확합니다. 부동소수점·가변 폭 정수에는 이 변환을 그대로 적용하지 않습니다.
문자열 키와 종료 기호 상태
사전순에서 a는 aa보다 먼저입니다. 끝을 실제 문자와 충돌하지 않는 가장 작은 기호로 취급할 수 있습니다. 바이트 문자열이라면 끝을 0, 실제 바이트 b를 b+1로 매핑해 총 257개 기호를 사용하면 실제 NUL 바이트도 구별됩니다.
LSD는 최대 길이까지 오른쪽 끝의 부족한 자리를 종료 기호로 채운 것으로 보고 가장 뒤 자리부터 안정 분배합니다. 매우 긴 문자열 하나 때문에 모든 짧은 문자열도 많은 단계를 거칠 수 있습니다. MSD는 첫 자리부터 같은 접두 그룹을 나누고 각 그룹의 다음 자리로 내려가며 종료 기호 그룹은 더 처리하지 않습니다. 깊은 공통 접두사는 재귀 깊이와 반복 스캔을 키웁니다.
UTF-8 바이트 사전순, 코드 포인트 순서, 사용자 언어의 collation은 같은 요구가 아닙니다. 정규화·대소문자·언어별 정렬 키를 먼저 정하고 그 키에 알고리즘을 적용해야 합니다.
기준 비교 정렬과 결과 대조
범위가 작은 정수·음수 최솟값·최댓값·0·동점 레코드·빈 문자열·접두 관계·NUL 바이트를 포함해 기준 비교 정렬과 대조합니다. 안정성이 필요하면 키뿐 아니라 원본 순번도 확인합니다.
키 범위와 자릿수가 커질 때 카운터·출력 버퍼·총 읽기/쓰기량을 측정합니다. 이미 정렬된 run을 활용하는 비교 정렬이 실제 데이터에서 더 유리할 수도 있습니다. “정수니까 선형”이라는 말 대신 n·R·d와 키 표현, 실제 이동량을 함께 설명해야 합니다.
실패를 좁힐 때는 먼저 동점 레코드의 순서가 깨졌는지 확인하고, 그 다음 자리 처리 방향·digit 범위·부호 변환·문자열 종료 기호를 각각 독립적으로 검사합니다. 예상 결과는 동일 키의 원본 순서 보존, signed 최소값과 0의 경계 정렬, 접두 문자열의 짧은 문자열 우선입니다. 어느 하나라도 어긋나면 성능 측정보다 먼저 키 표현 또는 안정성 계약을 고칩니다.