10. 기수 정렬 (Radix Sort) — O(d·n), 고정 자릿수

핵심 인사이트 (3줄 요약)

본질: 기수 정렬은 데이터를 자릿수(digit) 단위로 분리해 각 자릿수마다 안정 정렬을 반복 적용함으로써 O(d·n) 시간에 정수를 정렬한다.

가치: 자릿수 d가 상수에 가까운 고정 길이 데이터(전화번호, IP 주소, 주민번호 등)에서 O(n)에 수렴하며 대용량 정수 정렬에 강점을 보인다.

판단 포인트: 서브루틴으로 반드시 안정 정렬(계수 정렬)을 사용해야 하며, 문자열·실수처럼 고정 자릿수가 아닌 데이터에는 추가 처리가 필요하다.

Ⅰ. 개요 및 필요성

비교 정렬의 O(n log n) 한계를 넘기 위한 또 다른 접근이 **기수 정렬 (Radix Sort)**이다. 계수 정렬이 값의 전체 범위 k에 의존하는 반면, 기수 정렬은 각 자릿수(0~9, 26알파벳 등) 범위 k만 사용하므로 k가 고정된다(기수 진법 수). 32비트 정수도 10진수 10자리, 2진수 32비트로 분해하면 각 자릿수는 0~9 또는 0~1로 제한된다.

두 가지 처리 방향

방식	이름	설명
LSD	Least Significant Digit (최하위 자릿수 우선)	일의 자리부터 정렬 → 쉽고 안정적
MSD	Most Significant Digit (최상위 자릿수 우선)	최고 자리부터 정렬 → 재귀적, 사전식 정렬에 유리

📢 섹션 요약 비유: 기수 정렬은 우편번호로 편지를 분류하는 것과 같다. 먼저 마지막 자리 숫자로 분류하고, 그 다음 앞 자리로 분류하면 최종적으로 완벽한 순서가 된다.

Ⅱ. 아키텍처 및 핵심 원리

LSD 기수 정렬 ASCII 다이어그램

입력: [170, 45, 75, 90, 802, 24, 2, 66]

── 1라운드: 일의 자리(1s)로 안정 정렬 ─────────────
 0│ 170, 90
 2│ 802, 2
 4│ 24
 5│ 45, 75
 6│ 66
결과: [170, 90, 802, 2, 24, 45, 75, 66]

── 2라운드: 십의 자리(10s)로 안정 정렬 ─────────────
 0│ 802, 2
 2│ 24
 4│ 45
 6│ 66
 7│ 170, 75
 9│ 90
결과: [802, 2, 24, 45, 66, 170, 75, 90]

── 3라운드: 백의 자리(100s)로 안정 정렬 ────────────
 0│ 2, 24, 45, 66, 75, 90
 1│ 170
 8│ 802
결과: [2, 24, 45, 66, 75, 90, 170, 802] ✅

알고리즘 핵심 코드 흐름

┌─────────────────────────────────────────────────┐
│  RadixSort(arr, maxDigits d):                   │
│    for i = 1 to d:                              │
│      안정 정렬(arr, 기준=i번째 자릿수)           │
│      ↑ 계수 정렬(Counting Sort) 사용            │
│                                                 │
│  왜 안정 정렬이 필수인가?                        │
│  → 이전 자릿수 정렬 결과를 상위 자릿수 정렬이   │
│    덮어쓰지 않아야 함 (같은 상위 자리면 하위    │
│    자리 순서 유지)                               │
└─────────────────────────────────────────────────┘

시간/공간 복잡도

항목	복잡도	비고
시간 (전체)	O(d·(n+k))	d=자릿수, k=기수(진법)
d가 상수일 때	O(n)	32비트 정수: d=32(2진), d=10(10진)
공간	O(n+k)	계수 정렬 보조 배열
안정 정렬	✅	LSD 방식
제자리 정렬	❌	보조 배열 필요

📢 섹션 요약 비유: 기수 정렬은 다단계 파일 분류 시스템이다. 먼저 날짜의 일(day) 단위로 분류하고, 그다음 월(month), 마지막으로 년(year) 단위로 분류하면, 최종적으로 완벽한 날짜 순서가 만들어진다.

Ⅲ. 비교 및 연결

LSD vs MSD 비교

구분	LSD	MSD
처리 순서	최하위 자릿수 → 최상위	최상위 자릿수 → 최하위
구현	반복(Iterative)	재귀(Recursive)
안정성	✅ 안정	추가 처리 필요
적합 사례	고정 길이 정수	사전식 정렬, 가변 길이 문자열
메모리	O(n+k)	O(n+k·d) 재귀 스택

비비교 정렬 계열 비교

알고리즘	시간	공간	키 조건
계수 정렬 (Counting Sort)	O(n+k)	O(n+k)	k ≤ O(n)
기수 정렬 (Radix Sort)	O(d·(n+k))	O(n+k)	고정 자릿수
버킷 정렬 (Bucket Sort)	O(n) avg	O(n)	균등 분포

📢 섹션 요약 비유: 기수 정렬과 계수 정렬의 관계는 고속도로와 IC(인터체인지)의 관계다. 계수 정렬이 각 자릿수에서 효율적으로 분기(처리)하고, 기수 정렬이 전체 경로를 통합 관리한다.

Ⅳ. 실무 적용 및 기술사 판단

실제 적용 시나리오

시나리오 1 — 전화번호 정렬: 11자리 숫자 n=1억 건
→ d=11, k=10, 시간 = O(11·(10⁸+10)) ≈ O(n)
→ 비교 정렬 O(n log n) 대비 약 3.5배 빠름

시나리오 2 — IPv4 주소 정렬: 4바이트(8비트×4), k=256
→ d=4, 각 옥텟(Octet)별로 계수 정렬
→ 네트워크 라우팅 테이블 정렬에 활용

시나리오 3 — 해시 버킷 정렬: 해시값(고정 비트)으로 레코드 정렬
→ 데이터베이스 인덱스 구성 시 활용

기수 선택 트레이드오프

┌──────────────────────────────────────────────────────┐
│  기수(Radix) = 2  (2진수)                             │
│   → d = 32비트, 패스 횟수 많음, k=2 (매우 작은 배열) │
│                                                      │
│  기수(Radix) = 256 (1바이트)                          │
│   → d = 4 (32비트 정수), 패스 횟수 적음, k=256       │
│                                                      │
│  실무 권장: 기수 = 256 (바이트 단위)                  │
│  → 4패스로 32비트 정수 완전 정렬                      │
└──────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 기수 선택은 사탕을 몇 개씩 묶어 포장할지 결정하는 것과 같다. 한 개씩(2진수)이면 포장 횟수가 많고, 100개씩(256진수)이면 한 번에 많이 처리할 수 있다.

Ⅴ. 기대효과 및 결론

기수 정렬은 자릿수 분해라는 독창적 아이디어로 정수/고정 길이 데이터의 대규모 정렬 문제를 O(n)에 가깝게 해결한다. 데이터베이스 시스템, 네트워크 라우팅, 암호화 해시 처리 등 실무의 고성능 정렬 요구에 직접 대응한다.

효과 정리

효과	내용
성능	고정 자릿수 조건 충족 시 O(n) 수렴
안정성	LSD 방식에서 완벽한 안정 정렬
확장성	문자열, IP, 날짜 등 다양한 형식으로 확장 가능
캐시 효율	배열 기반으로 메모리 지역성(Locality) 양호

📢 섹션 요약 비유: 기수 정렬은 대용량 물류 센터 자동화 시스템이다. 바코드의 각 자리를 순서대로 스캔하면서 여러 컨베이어 벨트로 분류하면, 수백만 개 박스가 단 몇 번의 패스만으로 완벽하게 정렬된다.

📌 관련 개념 맵

개념	연결 관계	설명
계수 정렬 (Counting Sort)	→ 서브루틴	각 자릿수 정렬에 사용
버킷 정렬 (Bucket Sort)	유사 개념	값 분포 기반 분류
안정 정렬 (Stable Sort)	→ 필수 성질	LSD에서 이전 자릿수 보존
비교 기반 하한	↔ 돌파	Ω(n log n) 한계 우회
기수(Radix)	→ 설계 파라미터	기수 선택이 성능 결정

📈 관련 키워드 및 발전 흐름도

[비교 정렬 (O(n log n)) — 비교 기반 한계]
    │
    ▼
[계수 정렬 (Counting Sort) — 자릿수별 안정 정렬]
    │
    ▼
[LSD Radix Sort — 낮은 자릿수부터 반복]
    │
    ▼
[MSD Radix Sort — 높은 자릿수부터 재귀]
    │
    ▼
[고정 자릿수 정수/문자열 정렬 — 전화번호·IP·날짜]
    │
    ▼
[대용량 비비교 정렬 엔진 — DB·네트워크·검색 인덱스]

기수 정렬은 비교 정렬의 O(n log n) 한계를 자릿수 분해와 안정 정렬로 우회해, 고정 길이 키의 대용량 정렬을 빠르게 처리한다.

👶 어린이를 위한 3줄 비유 설명

📮 우편번호 분류: 편지를 우편번호 마지막 자리 → 그다음 자리 → 맨 앞 자리 순으로 분류하면, 마치 마법처럼 모든 편지가 순서대로 쌓여요.
🗂️ 서랍장 정리: 10개 서랍이 있고, 각 자릿수마다 한 번씩 정리하면 몇 번의 정리로 수백만 개도 완벽하게 정돈할 수 있어요.
🔢 자릿수 미용실: 숫자의 일의 자리, 십의 자리, 백의 자리를 차례로 꾸미면(정렬하면), 마지막엔 모두 아름답게 줄을 서 있어요!