11.10 기수 정렬¶
앞 절에서 배운 계수 정렬은 데이터 수 \(n\)은 많고 값의 범위 \(m\)은 작은 경우에 적합하다. 학번 \(n = 10^6\) 개를 정렬해야 하며, 학번이 \(8\) 자리 수라고 하자. 이때 값의 범위는 \(m = 10^8\)로 매우 커서 계수 정렬에는 많은 메모리가 필요하다. 기수 정렬을 사용하면 이 문제를 피할 수 있다.
기수 정렬(radix sort)의 핵심 아이디어는 계수 정렬과 같으며, 개수를 세어 정렬한다. 여기에 자릿수 사이의 순서 관계를 이용하여 각 자릿수를 차례로 정렬함으로써 최종 정렬 결과를 얻는다.
11.10.1 알고리즘 과정¶
학번을 예로 들어 가장 낮은 자리를 \(1\) 번째, 가장 높은 자리를 \(8\) 번째라고 하자. 기수 정렬의 과정은 아래 그림(11-18)과 같다.
- 자릿수 \(k = 1\)로 초기화한다.
- 학번의 \(k\) 번째 자리를 기준으로 '계수 정렬'을 수행한다. 완료하면 데이터는 \(k\) 번째 자리의 값에 따라 오름차순으로 정렬된다.
- \(k\)를 \(1\) 늘리고
2.단계로 돌아가 반복한다. 모든 자리를 정렬하면 종료한다.
그림 11-18 기수 정렬 알고리즘 과정
이제 코드 구현을 살펴보자. \(d\) 진법으로 표현한 수 \(x\)의 \(k\) 번째 자리 \(x_k\)는 다음 공식으로 구할 수 있다.
\[
x_k = \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d
\]
여기서 \(\lfloor a \rfloor\)는 부동 소수점 수 \(a\)를 내림하는 연산이고, \(\bmod \: d\)는 \(d\)로 나눈 나머지를 구하는 연산이다. 학번 데이터에서는 \(d = 10\)이고 \(k \in [1, 8]\)이다.
또한 수의 \(k\) 번째 자리를 기준으로 정렬할 수 있도록 계수 정렬 코드를 조금 수정해야 한다.
radix_sort.py
def digit(num: int, exp: int) -> int:
"""원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다"""
# k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num // exp) % 10
def counting_sort_digit(nums: list[int], exp: int):
"""계수 정렬(nums의 k번째 자릿값을 기준으로 정렬)"""
# 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
counter = [0] * 10
n = len(nums)
# 0~9 각 숫자의 등장 횟수를 센다
for i in range(n):
d = digit(nums[i], exp) # nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d] += 1 # 숫자 d의 등장 횟수를 센다
# 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for i in range(1, 10):
counter[i] += counter[i - 1]
# 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
res = [0] * n
for i in range(n - 1, -1, -1):
d = digit(nums[i], exp)
j = counter[d] - 1 # 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i] # 현재 원소를 인덱스 j에 채운다
counter[d] -= 1 # d의 개수를 1 줄인다
# 결과로 원래 배열 nums를 덮어쓴다
for i in range(n):
nums[i] = res[i]
def radix_sort(nums: list[int]):
"""기수 정렬"""
# 배열의 최댓값을 구하여 최대 자릿수를 판단한다
m = max(nums)
# 낮은 자리에서 높은 자리 순서로 순회한다
exp = 1
while exp <= m:
# 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
# k = 1 -> exp = 1
# k = 2 -> exp = 10
# 즉, exp = 10^(k-1)이다
counting_sort_digit(nums, exp)
exp *= 10
radix_sort.cpp
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
int digit(int num, int exp) {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num / exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
void countingSortDigit(vector<int> &nums, int exp) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
vector<int> counter(10, 0);
int n = nums.size();
// 0~9 각 숫자의 등장 횟수를 센다
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
vector<int> res(n, 0);
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (int i = 0; i < n; i++)
nums[i] = res[i];
}
/* 기수 정렬 */
void radixSort(vector<int> &nums) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
int m = *max_element(nums.begin(), nums.end());
// 낮은 자리에서 높은 자리 순서로 순회한다
for (int exp = 1; exp <= m; exp *= 10)
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp);
}
radix_sort.java
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
int digit(int num, int exp) {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num / exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
void countingSortDigit(int[] nums, int exp) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
int[] counter = new int[10];
int n = nums.length;
// 0~9 각 숫자의 등장 횟수를 센다
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (int i = 0; i < n; i++)
nums[i] = res[i];
}
/* 기수 정렬 */
void radixSort(int[] nums) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
int m = Integer.MIN_VALUE;
for (int num : nums)
if (num > m)
m = num;
// 낮은 자리에서 높은 자리 순서로 순회한다
for (int exp = 1; exp <= m; exp *= 10) {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp);
}
}
radix_sort.cs
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
int Digit(int num, int exp) {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num / exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
void CountingSortDigit(int[] nums, int exp) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
int[] counter = new int[10];
int n = nums.Length;
// 0~9 각 숫자의 등장 횟수를 센다
for (int i = 0; i < n; i++) {
int d = Digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) {
int d = Digit(nums[i], exp);
int j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (int i = 0; i < n; i++) {
nums[i] = res[i];
}
}
/* 기수 정렬 */
void RadixSort(int[] nums) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
int m = int.MinValue;
foreach (int num in nums) {
if (num > m) m = num;
}
// 낮은 자리에서 높은 자리 순서로 순회한다
for (int exp = 1; exp <= m; exp *= 10) {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
CountingSortDigit(nums, exp);
}
}
radix_sort.go
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
func digit(num, exp int) int {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num / exp) % 10
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
func countingSortDigit(nums []int, exp int) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
counter := make([]int, 10)
n := len(nums)
// 0~9 각 숫자의 등장 횟수를 센다
for i := 0; i < n; i++ {
d := digit(nums[i], exp) // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++ // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for i := 1; i < 10; i++ {
counter[i] += counter[i-1]
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
res := make([]int, n)
for i := n - 1; i >= 0; i-- {
d := digit(nums[i], exp)
j := counter[d] - 1 // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i] // 현재 원소를 인덱스 j에 채운다
counter[d]-- // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for i := 0; i < n; i++ {
nums[i] = res[i]
}
}
/* 기수 정렬 */
func radixSort(nums []int) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
max := math.MinInt
for _, num := range nums {
if num > max {
max = num
}
}
// 낮은 자리에서 높은 자리 순서로 순회한다
for exp := 1; max >= exp; exp *= 10 {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp)
}
}
radix_sort.swift
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
func digit(num: Int, exp: Int) -> Int {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
(num / exp) % 10
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
func countingSortDigit(nums: inout [Int], exp: Int) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
var counter = Array(repeating: 0, count: 10)
// 0~9 각 숫자의 등장 횟수를 센다
for i in nums.indices {
let d = digit(num: nums[i], exp: exp) // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d] += 1 // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for i in 1 ..< 10 {
counter[i] += counter[i - 1]
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
var res = Array(repeating: 0, count: nums.count)
for i in nums.indices.reversed() {
let d = digit(num: nums[i], exp: exp)
let j = counter[d] - 1 // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i] // 현재 원소를 인덱스 j에 채운다
counter[d] -= 1 // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for i in nums.indices {
nums[i] = res[i]
}
}
/* 기수 정렬 */
func radixSort(nums: inout [Int]) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
var m = Int.min
for num in nums {
if num > m {
m = num
}
}
// 낮은 자리에서 높은 자리 순서로 순회한다
for exp in sequence(first: 1, next: { m >= ($0 * 10) ? $0 * 10 : nil }) {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums: &nums, exp: exp)
}
}
radix_sort.js
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
function digit(num, exp) {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return Math.floor(num / exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
function countingSortDigit(nums, exp) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
const counter = new Array(10).fill(0);
const n = nums.length;
// 0~9 각 숫자의 등장 횟수를 센다
for (let i = 0; i < n; i++) {
const d = digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (let i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
const res = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const d = digit(nums[i], exp);
const j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (let i = 0; i < n; i++) {
nums[i] = res[i];
}
}
/* 기수 정렬 */
function radixSort(nums) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
let m = Math.max(... nums);
// 낮은 자리에서 높은 자리 순서로 순회한다
for (let exp = 1; exp <= m; exp *= 10) {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp);
}
}
radix_sort.ts
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
function digit(num: number, exp: number): number {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return Math.floor(num / exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
function countingSortDigit(nums: number[], exp: number): void {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
const counter = new Array(10).fill(0);
const n = nums.length;
// 0~9 각 숫자의 등장 횟수를 센다
for (let i = 0; i < n; i++) {
const d = digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (let i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
const res = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const d = digit(nums[i], exp);
const j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (let i = 0; i < n; i++) {
nums[i] = res[i];
}
}
/* 기수 정렬 */
function radixSort(nums: number[]): void {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
let m: number = Math.max(... nums);
// 낮은 자리에서 높은 자리 순서로 순회한다
for (let exp = 1; exp <= m; exp *= 10) {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp);
}
}
radix_sort.dart
/* 원소 _num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
int digit(int _num, int exp) {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (_num ~/ exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
void countingSortDigit(List<int> nums, int exp) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
List<int> counter = List<int>.filled(10, 0);
int n = nums.length;
// 0~9 각 숫자의 등장 횟수를 센다
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
List<int> res = List<int>.filled(n, 0);
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (int i = 0; i < n; i++) nums[i] = res[i];
}
/* 기수 정렬 */
void radixSort(List<int> nums) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
// Dart에서 int의 길이는 64비트이다
int m = -1 << 63;
for (int _num in nums) if (_num > m) m = _num;
// 낮은 자리에서 높은 자리 순서로 순회한다
for (int exp = 1; exp <= m; exp *= 10)
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp);
}
radix_sort.rs
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
fn digit(num: i32, exp: i32) -> usize {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return ((num / exp) % 10) as usize;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
fn counting_sort_digit(nums: &mut [i32], exp: i32) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
let mut counter = [0; 10];
let n = nums.len();
// 0~9 각 숫자의 등장 횟수를 센다
for i in 0..n {
let d = digit(nums[i], exp); // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d] += 1; // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for i in 1..10 {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
let mut res = vec![0; n];
for i in (0..n).rev() {
let d = digit(nums[i], exp);
let j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d] -= 1; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
nums.copy_from_slice(&res);
}
/* 기수 정렬 */
fn radix_sort(nums: &mut [i32]) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
let m = *nums.into_iter().max().unwrap();
// 낮은 자리에서 높은 자리 순서로 순회한다
let mut exp = 1;
while exp <= m {
counting_sort_digit(nums, exp);
exp *= 10;
}
}
radix_sort.c
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
int digit(int num, int exp) {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num / exp) % 10;
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
void countingSortDigit(int nums[], int size, int exp) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
int *counter = (int *)malloc((sizeof(int) * 10));
memset(counter, 0, sizeof(int) * 10); // 이후 메모리 해제를 지원하도록 0으로 초기화한다
// 0~9 각 숫자의 등장 횟수를 센다
for (int i = 0; i < size; i++) {
// nums[i]의 k번째 자릿값을 구하여 d로 표시한다
int d = digit(nums[i], exp);
// 숫자 d의 등장 횟수를 센다
counter[d]++;
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
int *res = (int *)malloc(sizeof(int) * size);
for (int i = size - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i]; // 현재 원소를 인덱스 j에 채운다
counter[d]--; // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (int i = 0; i < size; i++) {
nums[i] = res[i];
}
// 메모리 해제
free(res);
free(counter);
}
/* 기수 정렬 */
void radixSort(int nums[], int size) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
int max = INT32_MIN;
for (int i = 0; i < size; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
// 낮은 자리에서 높은 자리 순서로 순회한다
for (int exp = 1; max >= exp; exp *= 10)
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, size, exp);
}
radix_sort.kt
/* 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 */
fun digit(num: Int, exp: Int): Int {
// k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
return (num / exp) % 10
}
/* 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬) */
fun countingSortDigit(nums: IntArray, exp: Int) {
// 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
val counter = IntArray(10)
val n = nums.size
// 0~9 각 숫자의 등장 횟수를 센다
for (i in 0..<n) {
val d = digit(nums[i], exp) // nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d]++ // 숫자 d의 등장 횟수를 센다
}
// 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
for (i in 1..9) {
counter[i] += counter[i - 1]
}
// 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
val res = IntArray(n)
for (i in n - 1 downTo 0) {
val d = digit(nums[i], exp)
val j = counter[d] - 1 // 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i] // 현재 원소를 인덱스 j에 채운다
counter[d]-- // d의 개수를 1 줄인다
}
// 결과로 원래 배열 nums를 덮어쓴다
for (i in 0..<n)
nums[i] = res[i]
}
/* 기수 정렬 */
fun radixSort(nums: IntArray) {
// 배열의 최댓값을 구하여 최대 자릿수를 판단한다
var m = Int.MIN_VALUE
for (num in nums) if (num > m) m = num
var exp = 1
// 낮은 자리에서 높은 자리 순서로 순회한다
while (exp <= m) {
// 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 즉, exp = 10^(k-1)이다
countingSortDigit(nums, exp)
exp *= 10
}
}
radix_sort.rb
### 원소 num의 k번째 자릿값 반환. 이때 exp = 10^(k-1)이다 ###
def digit(num, exp)
# k 대신 exp를 전달하면 여기서 비용이 큰 거듭제곱 계산을 반복하지 않아도 된다
(num / exp) % 10
end
### 계수 정렬(nums의 k번째 자릿값을 기준으로 정렬)###
def counting_sort_digit(nums, exp)
# 십진수의 각 자리는 0~9 범위이므로 길이가 10인 버킷 배열이 필요하다
counter = Array.new(10, 0)
n = nums.length
# 0~9 각 숫자의 등장 횟수를 센다
for i in 0...n
d = digit(nums[i], exp) # nums[i]의 k번째 자릿값을 구하여 d로 표시한다
counter[d] += 1 # 숫자 d의 등장 횟수를 센다
end
# 접두 합을 구하여 등장 개수를 배열 인덱스로 변환한다
(1...10).each { |i| counter[i] += counter[i - 1] }
# 역순으로 순회하며 버킷에 집계된 결과에 따라 각 원소를 res에 채운다
res = Array.new(n, 0)
for i in (n - 1).downto(0)
d = digit(nums[i], exp)
j = counter[d] - 1 # 배열에서 d의 인덱스 j를 구한다
res[j] = nums[i] # 현재 원소를 인덱스 j에 채운다
counter[d] -= 1 # d의 개수를 1 줄인다
end
# 결과로 원래 배열 nums를 덮어쓴다
(0...n).each { |i| nums[i] = res[i] }
end
### 기수 정렬 ###
def radix_sort(nums)
# 배열의 최댓값을 구하여 최대 자릿수를 판단한다
m = nums.max
# 낮은 자리에서 높은 자리 순서로 순회한다
exp = 1
while exp <= m
# 배열 원소의 k번째 자릿값에 대해 계수 정렬을 수행한다
# k = 1 -> exp = 1
# k = 2 -> exp = 10
# 즉, exp = 10^(k-1)이다
counting_sort_digit(nums, exp)
exp *= 10
end
end
코드 시각화
왜 가장 낮은 자리부터 정렬하는가?
여러 차례 연속으로 정렬하면 뒤의 정렬 결과가 앞의 결과를 덮어쓴다. 예를 들어 첫 번째 정렬에서는 \(a < b\)였지만 두 번째 정렬에서는 \(a > b\)라면, 두 번째 결과가 첫 번째 결과를 대신한다. 높은 자릿수가 낮은 자릿수보다 우선하므로 낮은 자리부터 정렬한 뒤 높은 자리를 정렬해야 한다.
11.10.2 알고리즘 특성¶
기수 정렬은 계수 정렬보다 값의 범위가 큰 경우에 적합하다. 단, 데이터를 고정된 자릿수의 형식으로 표현할 수 있어야 하며 자릿수가 지나치게 크면 안 된다. 예를 들어 부동 소수점 수는 자릿수 \(k\)가 너무 커서 시간 복잡도가 \(O(nk) \gg O(n^2)\)이 될 수 있으므로 기수 정렬에 적합하지 않다.
- 시간 복잡도 \(O(nk)\), 비적응형 정렬: 데이터 수가 \(n\), 진법이 \(d\), 최대 자릿수가 \(k\)라면 한 자리를 계수 정렬하는 데 \(O(n + d)\) 시간이 걸리고, \(k\) 자리 전체를 정렬하는 데 \(O((n + d)k)\) 시간이 걸린다. 일반적으로 \(d\)와 \(k\)는 모두 비교적 작으므로 시간 복잡도는 \(O(n)\)에 가까워진다.
- 공간 복잡도 \(O(n + d)\), 제자리 정렬이 아님: 계수 정렬과 마찬가지로 길이가 \(n\)과 \(d\)인 배열
res와counter가 필요하다. - 안정 정렬: 계수 정렬이 안정적이면 기수 정렬도 안정적이다. 계수 정렬이 불안정하면 기수 정렬은 올바른 정렬 결과를 보장할 수 없다.