개념
- 숫자의 자릿수별로 차례대로 정렬해 나가는 방법
- 비교 기반이 아닌 정렬
- 한 자리씩 (1의 자리, 10의 자리, 100의 자리...) 순서대로 정렬
- 각 자릿수 정렬은 주로 Counting Sort를 사용해서 안정적으로(stable) 처리
사용방식
- 가장 작은 자리수부터 정렬 (LSD: Least Significant Digit)
- Counting Sort로 해당 자리만 기준으로 정렬
- 다음 자리수로 이동해서 반복
사용처
- 수가 작은 정수일 때 (자릿수 작음)
- 문자열 길이가 고정돼 있을 때
- ID 번호, 학번처럼 포맷이 일정한 데이터
- ※ 일반 정렬이 더 나을 수 있으니 남용 x {문자 길이 우선 정렬 등 <- 문자열 길이가 일관x}*
주의 사항
- Counting Sort 메모리 소모 주의
시간 복잡도
단계 | 시간 |
---|---|
각 자리별 정렬 | O(N + K) |
자리 수 (d자리)만큼 반복 | d번 |
'공부 > 알고리즘공부' 카테고리의 다른 글
Counting Sort (0) | 2025.04.29 |
---|---|
2진수의 사칙연산 (0) | 2025.03.01 |
정렬알고리즘 #단순정렬 (0) | 2022.07.11 |
In-place & Stable ? (0) | 2022.05.01 |
Two Point 알고리즘 (0) | 2022.04.29 |