자료구조 - 기수 정렬

[기수 정렬(Radix Sort)]

기수 정렬(Radix Sort)은 비교 기반의 정렬 알고리즘이 아닌 자릿수를 기준으로 정렬하는 알고리즘입니다. 리스트의 모든 요소를 자릿수 별로 비교하여 정렬합니다.

일반적으로 10진수의 경우 각 자릿수(1의 자리, 10의 자리, 100의 자리, ...)를 기준으로 정렬합니다.

기수 정렬은 정수형 데이터에 대해 특히 효과적이며, 시간 복잡도는 O(d⋅(n+k)) 입니다.

여기서 ddd는 가장 큰 수의 자릿수, nnn은 리스트의 길이, kkk는 기수(보통 10)입니다.

 

 

기수 정렬 과정

1. 리스트의 가장 작은 자릿수(1의 자리)부터 가장 큰 자릿수까지 반복하여 정렬합니다.
2. 각 자릿수 별로 리스트를 정렬하기 위해 안정적인 정렬 알고리즘(보통은 계수 정렬)을 사용합니다.

 

기수 정렬 의사 코드

함수 getMaxDigit(arr):
    maxNum = 리스트 arr에서 가장 큰 수
    digit = 0
    while maxNum > 0:
        maxNum을 10으로 나눔
        digit 증가
    반환 digit

함수 radixSort(arr, digit):
    n = 배열의 길이(arr)
    buckets[0..9] = 빈 리스트로 초기화 // 0~9까지의 버킷

    for d = 1부터 digit까지:
        for i = 0부터 n-1까지:
            index = (arr[i] / (10^(d-1))) % 10 // 현재 자릿수의 값 추출
            buckets[index].append(arr[i]) // 버킷에 추가

        arr의 모든 요소를 버킷에 있는 순서대로 재배치

        for j = 0부터 9까지:
            buckets[j]를 비움 // 버킷 초기화

 

 

기수 정렬 예제

예시 리스트: [170, 45, 75, 90, 802, 24, 2, 66]

최대 자릿수 구하기:
    먼저 주어진 리스트에서 가장 큰 수의 자릿수를 구합니다. 예제 리스트에서 가장 큰 수는 802이며, 이의 자릿수는 3입니다.

1의 자릿수를 기준으로 버킷에 분배:
    1의 자릿수를 기준으로 리스트를 버킷에 분배합니다. 각 버킷에는 해당하는 자릿수의 숫자들이 들어가게 됩니다.

버킷 0: [170, 90]
버킷 1: [801, 2]
버킷 2: [2]
버킷 3: []
버킷 4: [24]
버킷 5: [45, 75]
버킷 6: [66]
버킷 7: []
버킷 8: []
버킷 9: []

버킷에 있는 순서대로 리스트 재배치:
    각 버킷에 있는 숫자들을 순서대로 리스트에 다시 넣어줍니다.

정렬된 리스트: [170, 90, 801, 2, 2, 24, 45, 75, 66]


10의 자릿수를 기준으로 버킷에 분배 및 정렬:
    이제는 10의 자릿수를 기준으로 리스트를 버킷에 분배하고 정렬합니다.

버킷 0: [801, 2, 2, 24, 45, 66]
버킷 1: [75]
버킷 2: [90]
버킷 3: []
버킷 4: []
버킷 5: [170, 801, 2, 24, 45, 66]
버킷 6: []
버킷 7: []
버킷 8: []
버킷 9: []

100의 자릿수를 기준으로 버킷에 분배 및 정렬:
    이번에는 100의 자릿수를 기준으로 리스트를 분배하고 정렬합니다. 현재 예제 리스트는 100의 자릿수가 없으므로 정렬이 끝납니다.

정렬된 리스트 출력:
    기수 정렬이 끝나면 최종적으로 정렬된 리스트가 출력됩니다.

최종 결과 리스트: [2, 2, 24, 45, 66, 75, 90, 170, 801]

 

 

기수 정렬 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 리스트의 가장 큰 수의 자릿수를 반환
int getMaxDigit(vector<int>& arr)
{
    int maxNum = *max_element(arr.begin(), arr.end());
    int digit = 0;
    while (maxNum > 0) 
    {
        maxNum /= 10;
        digit++;
    }
    return digit;
}

// 기수 정렬 함수 (리스트, 자릿수)
void radixSort(vector<int>& arr, int digit) 
{
    int n = arr.size();
    vector<vector<int>> buckets(10); // 0~9까지의 버킷

    // 각 자릿수 별로 정렬
    for (int d = 1; d <= digit; d++) 
    {
        // 각 자릿수 별로 버킷에 분배
        for (int num : arr) 
        {
            int index = (num / static_cast<int>(pow(10, d - 1))) % 10;
            buckets[index].push_back(num);
        }

        // 버킷에 저장된 값을 리스트에 복사
        int idx = 0;
        for (auto& bucket : buckets) 
        {
            for (int num : bucket)
            {
                arr[idx++] = num;
            }
            bucket.clear(); // 버킷 비우기
        }
    }
}

int main() 
{
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66}; // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    int digit = getMaxDigit(arr); // 최대 자릿수 계산
    radixSort(arr, digit); // 기수 정렬 수행

    cout << "정렬 후: ";
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}