[c++] 기수정렬

12 Dec 2023

기수정렬의 핵심 아이디어는 작은 수와 큰 수의 자릿수에 따라 정렬하는 것입니다. 예를 들어, 10진수의 경우 일의 자리부터 시작하여 십의 자리, 백의 자리 등과 같은 자릿수를 차례로 비교하면서 정렬을 수행합니다.

다음은 C++에서 기수정렬을 구현한 예제 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr, int exp) {
    vector<int> output(arr.size());
    vector<int> count(10, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[(arr[i] / exp) % 10]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

기수정렬은 안정적인 정렬 알고리즘이며, 시간 복잡도는 O(nk)입니다. 여기서 n은 입력 크기이고, k는 데이터의 최대 자릿수를 나타냅니다. 기수정렬은 데이터 크기에 상관없이 안정적인 성능을 보여주기 때문에 대규모 데이터에 대해서도 효율적으로 동작합니다.

기수정렬은 고정된 범위의 정수나 동일한 길이의 문자열과 같이 특정 자릿수로 정렬이 가능한 데이터에 대해 유용하게 활용될 수 있습니다.

참고 자료:

Introduction to the Design & Analysis of Algorithms (Anany Levitin)