기수 정렬
마지막 업데이트
기수 정렬은 정수를 위한 비교하지 않는 정렬입니다. 값을 비교하는 대신 숫자를 자릿수별로 정렬합니다. 최하위 자릿수(LSD) 버전은 먼저 일의 자리를, 다음으로 십의 자리, 그다음 백의 자리를 처리하며 각 자릿수에서 안정적인 계수 정렬을 사용합니다. 각 패스가 안정적이므로 최상위 자릿수를 처리하고 나면 배열 전체가 정렬됩니다. 위의 재생 버튼을 눌러 각 자릿수 패스가 막대를 어떻게 재배열하는지 확인하세요.
기수 정렬은 O(d·(n + k)) 시간에 동작하며, 여기서 d는 자릿수, k는 기수(여기서는 10)입니다. 고정 폭 정수의 경우 사실상 선형이며 O(n log n) 비교 정렬을 능가할 수 있지만, 자릿수나 키로 분해할 수 있는 데이터에서만 작동합니다.
시간 및 공간 복잡도
| 경우 | 복잡도 | 비고 |
|---|---|---|
| 시간 | O(d·(n + k)) | d 자릿수, 기수 k (d가 고정이면 선형) |
| 공간 | O(n + k) | 출력 배열 + 자릿수 카운트 |
| 안정성 | 예 | 각 자릿수 패스는 안정적인 계수 정렬 |
| 비교 기반? | 아니오 | 값을 비교하지 않고 자릿수로 정렬 |
| 적용 대상 | 정수/키 | 일반 비교 가능 객체에는 부적합 |
단계별 과정
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 처리할 자릿수를 알기 위해 최댓값을 찾는다. |
| 2 | 최하위 자릿수(일의 자리)부터 시작한다. |
| 3 | 계수 정렬을 사용해 해당 자릿수 기준으로 배열을 안정적으로 정렬한다. |
| 4 | 다음으로 더 높은 자릿수로 이동한다. |
| 5 | 모든 자릿수 위치를 처리할 때까지 반복한다. |
예제 풀이
[170, 45, 75, 90, 2, 24, 66] 정렬:
| 패스 | 배열 | 동작 |
|---|---|---|
| 시작 | [170, 45, 75, 90, 2, 24, 66] | 최댓값이 170이므로 자릿수 패스가 세 번 필요하다. |
| 일의 자리 | [170, 90, 2, 24, 45, 75, 66] | 일의 자리 기준 안정 정렬: 0, 0, 2, 4, 5, 5, 6. |
| 십의 자리 | [2, 24, 45, 66, 170, 75, 90] | 십의 자리 기준 안정 정렬: 0, 2, 4, 6, 7, 7, 9 (170이 75보다 앞선 순서를 유지). |
| 백의 자리 | [2, 24, 45, 66, 75, 90, 170] | 백의 자리 기준 안정 정렬. 170만 1을 가지므로 맨 뒤로 이동. 정렬 완료. |
기수 정렬을 사용해야 할 때
| 사용하면 좋은 경우 | 피해야 하는 경우 |
|---|---|
| 키가 자릿수로 나눌 수 있는 정수나 고정 길이 문자열일 때. | 사용자 정의 비교자로 임의의 객체를 정렬해야 할 때. |
키의 자릿수 d가 작고 유한하여 O(d·(n + k))가 O(n log n)을 능가할 때. | 키가 매우 길거나 무한하여 d가 커지고 각 패스가 비싸질 때. |
안정적인 정렬이 필요하고 O(n + k)의 추가 공간을 감당할 수 있을 때. | 메모리가 부족하여 O(n + k) 버퍼를 감당할 수 없을 때. |
값의 범위나 기수 k가 n에 비해 적당할 때. | k가 매우 커서 각 계수 정렬 패스가 실행 시간을 지배할 때. |
Radix Sort 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Radix Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Radix Sort 코드
Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))JavaScript로 구현한 Radix Sort 코드
JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Java로 구현한 Radix Sort 코드
Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}C++로 구현한 Radix Sort 코드
C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}C로 구현한 Radix Sort 코드
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}기수 정렬 자주 묻는 질문
기수 정렬의 시간 복잡도는 무엇인가요?
기수 정렬은
O(d·(n + k))이며, 여기서 d는 자릿수, k는 기수입니다. 고정 폭 정수의 경우 사실상 O(n)이 되어 비교 정렬보다 빠를 수 있습니다. O(n + k)의 추가 공간을 사용합니다.기수 정렬은 안정적인가요?
예. LSD 기수 정렬은 각 자릿수에서 안정적인 계수 정렬에 의존하며, 이 안정성 덕분에 자릿수별 접근 방식이 올바르게 정렬된 결과를 만들어냅니다.
기수 정렬은 언제 사용할 수 있나요?
기수 정렬은 정수나 고정 길이 문자열처럼 자릿수나 고정 크기 키로 분해할 수 있는 데이터에서 작동합니다. 범용 비교 정렬이 아니므로 사용자 정의 비교자로 임의의 객체를 정렬할 수는 없습니다.
기수 정렬은 계수 정렬과 어떻게 다른가요?
계수 정렬은 하나의 키로 한 번의 패스에서 정렬하며 값 범위만큼 큰 카운트 배열이 필요하므로 값이 넓게 퍼져 있으면 성능이 저하됩니다. 기수 정렬은 계수 정렬을 자릿수별로 적용하여 각 패스의 카운트 배열을 작게(기수
k) 유지하므로, 단순 계수 정렬로는 처리할 수 없는 큰 값 범위를 다룰 수 있습니다.왜 LSD 기수 정렬은 최하위 자릿수부터 시작하나요?
최하위 자릿수부터 시작하면 각 안정 패스가 이전의 더 낮은 자릿수들이 확립한 순서를 보존할 수 있습니다. 최상위 자릿수를 처리할 때쯤이면 그 자릿수가 같은 요소들은 이미 하위 자릿수에 의해 올바르게 정렬되어 있어, 배열이 최종적으로 완전히 정렬됩니다. 최상위 자릿수부터 먼저 정렬하면 이것이 깨지고 다른 재귀적 접근(MSD 기수 정렬)이 필요해집니다.
기수 정렬은 음수를 처리할 수 있나요?
직접적으로는 불가능합니다. 기본적인 자릿수 추출은 음이 아닌 정수를 가정합니다. 흔한 해결책은 최솟값을 더해 모든 값을 음이 아니게 오프셋하거나, 음수와 음이 아닌 수를 따로 정렬한 뒤 이어 붙이는 것입니다. 이를 무시하는 것은 기수 정렬을 실제 데이터에 적용할 때 자주 발생하는 버그입니다.
관련 자료
더 많은 시각화
