래딕스정렬 시각화
일의 자리부터 높은 자리까지 10개 버킷에 분배·수집하는 LSD 래딕스정렬 과정을 관찰합니다
정렬★★☆
속도
1 / 1현재 자릿수: -동작:
배열 크기14
분배 중수집 중버킷 내 원소
각 자릿수 패스에서 원소가 10개 버킷(0-9)에 분배되고 순서대로 수집되는 과정을 관찰하세요.
래딕스정렬이란?
래딕스정렬(Radix Sort)은 자릿수(digit)를 기준으로 정렬하는 비교 없는 정렬 알고리즘입니다. LSD(Least Significant Digit) 방식은 가장 낮은 자리(일의 자리)부터 시작해 높은 자리 순으로 카운팅정렬을 반복합니다. 시간 복잡도 O(d×n)으로, d(자릿수)가 작을 때 매우 빠르며 안정 정렬입니다.
사용 방법
- 1배열 크기를 조절하고 랜덤 또는 같은 자릿수 버튼으로 입력을 생성하세요
- 2재생 버튼으로 LSD 래딕스정렬 애니메이션을 시작하세요
- 3각 자릿수 패스에서 원소가 0-9 버킷에 분배되고 순서대로 수집되는 과정을 관찰하세요
- 4하이라이트된 자릿수 박스로 현재 정렬 기준 자릿수를 확인하세요
동작 원리
- 1가장 낮은 자릿수(LSD)부터 시작합니다
- 2현재 자릿수 기준으로 0~9 버킷에 분배합니다
- 3버킷 순서대로 수집하여 배열을 재구성합니다
- 4다음 자릿수로 이동하여 분배·수집을 반복합니다
- 5최고 자릿수까지 완료하면 정렬이 종료됩니다. O(d × n) (d=자릿수)
실무 활용
- •우편번호 정렬 — 자릿수가 고정(5~6자리)이라 O(n)에 가깝습니다
- •대량의 정수/문자열 정렬(전화번호, IP 주소)에 사용됩니다
- •카드 정렬기(IBM 펀치카드 시대부터 사용된 역사적 알고리즘)입니다
- •병렬 GPU 정렬 — 래딕스정렬은 병렬화에 매우 적합합니다
- •데이터베이스의 대량 정수 키 인덱스 구축에 활용됩니다
비슷한 알고리즘
- •퀵정렬/병합정렬 O(n log n) — 비교 기반 정렬은 범용적이지만 래딕스정렬은 키 길이가 짧으면 더 빠릅니다
- •카운팅정렬 — 래딕스정렬의 내부에서 각 자릿수별로 사용되는 서브루틴입니다
- •MSD(Most Significant Digit) 래딕스 — 높은 자릿수부터 정렬. 조기 종료 가능하나 재귀가 필요합니다
학습 팁
- •LSD는 낮은 자리부터 정렬하므로 안정 정렬이어야 올바르게 동작합니다
- •각 패스는 카운팅정렬(O(n+10)=O(n))을 수행하므로 전체는 O(d×n)입니다
- •같은 자릿수 버튼으로 d가 일정한 경우를, 랜덤으로 d가 다른 경우를 비교해보세요
- •숫자 범위가 크더라도 자릿수(d)가 작으면 매우 빠릅니다 (예: 64비트 정수 d=19)
자주 묻는 질문
Q. LSD vs MSD 래딕스정렬 차이는?
A. LSD(최하위 자릿수부터)는 구현이 단순하고 안정적입니다. MSD(최상위 자릿수부터)는 재귀적으로 동작하며 문자열 정렬에 유리합니다. 이 시각화는 LSD 방식을 사용합니다.
Q. 어떤 경우에 빠른가요?
A. 자릿수(d)가 고정되어 있거나 작을 때 (예: 전화번호, 우편번호, 날짜 YYYYMMDD). d×n < n log n이면 비교 정렬보다 빠릅니다.