기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)

자릿수별로 안정 정렬을 반복하여 정수를 정렬하는 비비교 기반 알고리즘

목적: 선형 시간 정렬, 큰 정수

특징: 비비교 기반, 안정 정렬, 자릿수 의존, 계수 정렬 활용

동작: ① LSD(Least Significant Digit) - 가장 낮은 자릿수부터 → ② 각 자릿수별로 안정 정렬(계수 정렬) → ③ 최상위 자릿수까지 반복

LSD vs MSD: LSD(오른쪽→왼쪽, 단순), MSD(왼쪽→오른쪽, 재귀, 조기 종료)

시간 복잡도: O(d × (n + k)) - d = 자릿수, k = 기수(보통 10)

공간 복잡도: O(n + k) - 계수 정렬 공간

장점: 선형 시간(자릿수 적으면), 안정 정렬, 큰 정수 효율

단점: 자릿수 많으면 느림, 추가 메모리, 정수만, 비교 정렬보다 느릴 수 있음

적용사례: 큰 정수 정렬, 문자열 정렬(고정 길이), 카드 덱 정렬

비교: 기수(O(d(n+k))/자릿수) vs 계수(O(n+k)/범위) vs 퀵(O(n log n)/비교)

연관: 계수 정렬, LSD, MSD, 비비교 정렬