에듀테크 프로젝트 대시보드
기수 정렬 (Radix Sort)
숫자를 서로 비교하지 않고 정렬하는 방법. 가장 낮은 자릿수(1의 자리)부터 차례로 보면서 0~9번 버킷(양동이)에 나눠 담았다가 순서대로 다시 꺼내기를 반복한다. 자릿수를 한 번 훑을 때마다 배열이 조금씩 정렬되고, 가장 높은 자릿수까지 끝나면 완전히 정렬된다.
< 로 비교하는 정렬은 아무리 잘 짜도 O(n log n) 보다 빠를 수 없다(비교 정렬의 하한). 기수 정렬은 비교를 아예 하지 않기 때문에 이 벽을 넘어 O(d·(n+k)) 에 정렬한다. (d = 자릿수, k = 진법, 보통 10)
LSD(Least Significant Digit)는 낮은 자리부터 처리하는 방식이다. 「한 자리 진행」을 누르면 현재 자릿수 기준으로 모든 원소를 버킷에 담고(분배), 버킷 0→9 순서로 다시 배열에 꺼낸다(수집). 이 과정을 가장 큰 수의 자릿수만큼 반복한다.
329 와 91 을 생각해 보자. 높은 자리(백의 자리)부터 비교하면 91 은 091 로 봐서 백의 자리가 0, 329 는 3 → 이미 순서가 갈린다. 하지만 이렇게 하면 백의 자리가 같은 무리를 다시 독립적으로 쪼개 정렬해야 해서 재귀가 필요하다(MSD 방식).
LSD는 반대로 1의 자리 → 10의 자리 → 100의 자리 순으로 매번 전체 배열을 한 번씩만 안정 정렬한다. 마지막(가장 높은) 자리로 정렬하는 순간, 그 자리가 같은 원소들은 바로 앞 통과에서 이미 낮은 자리 기준으로 정렬돼 있으므로 전체가 정렬된다.
| 단계 | 기준 | 배열 상태 (예시) |
|---|---|---|
| 시작 | — | 329 457 657 839 436 720 355 008 091 |
| Pass 1 | 1의 자리 | 720 091 329 355 436 457 657 008 839 |
| Pass 2 | 10의 자리 | 008 720 329 436 839 355 457 657 091 |
| Pass 3 | 100의 자리 | 008 091 329 355 436 457 657 720 839 ✅ |
각 통과에서 "버킷에 담았다 꺼내기"는 사실 계수 정렬이다. 값의 범위가 0 ~ k 로 작을 때, 각 값이 몇 번 나오는지 세어 누적합을 구하면 각 원소가 갈 최종 위치를 비교 없이 바로 계산할 수 있다.
# 계수 정렬: 0..k 범위 정수 배열 a 를 안정 정렬 def counting_sort(a, k, key=lambda x: x): count = [0] * (k + 1) for x in a: # 1) 도수 세기 count[key(x)] += 1 for i in range(1, k + 1): # 2) 누적합 → 위치 경계 count[i] += count[i - 1] out = [0] * len(a) for x in reversed(a): # 3) 뒤에서부터 채워야 안정적 d = key(x) count[d] -= 1 out[count[d]] = x return out
# LSD 기수 정렬: 음이 아닌 정수 배열 def radix_sort(a, base=10): if not a: return a max_v = max(a) exp = 1 while max_v // exp > 0: # 자릿수만큼 반복 a = counting_sort(a, base - 1, key=lambda x, e=exp: (x // e) % base) exp *= base return a
| 정렬 | 평균 시간 | 추가 메모리 | 비교 기반? | 안정? |
|---|---|---|---|---|
| 퀵 정렬 | O(n log n) | O(log n) | 예 | 아니오 |
| 병합 정렬 | O(n log n) | O(n) | 예 | 예 |
| 계수 정렬 | O(n + k) | O(n + k) | 아니오 | 예 |
| 기수 정렬 (LSD) | O(d·(n + k)) | O(n + k) | 아니오 | 예 |
공짜는 아니다. 기수 정렬이 유리하려면 자릿수 d 가 작아야 한다. 32비트 정수를 10진法으로 처리하면 d ≈ 10. 값들이 0 ~ n100 처럼 극단적으로 크면 d 가 커져 O(n log n) 비교 정렬이 오히려 낫다. 또한 임의의 객체를 정수 키로 바꿀 수 있어야 하고, 버킷용 메모리 O(n+k) 가 필요하다.