[c++] 기수 정렬

12 Dec 2023

기수 정렬 알고리즘의 핵심 아이디어는 숫자를 자릿수 단위로 비교하지 않고, 숫자의 자릿수에 따라 일치 그룹으로 분류하는 것입니다. 각 자릿수의 범위는 숫자 시스템에 따라 다르며, 보통 10진수에서는 0부터 9까지의 숫자를 사용합니다.

기수 정렬은 가장 낮은 자릿수부터 시작하여 가장 높은 자릿수까지 차례로 정렬하는 방식으로 동작합니다. 각 단계에서는 일치 그룹으로 숫자를 모으고, 해당 자릿수를 기준으로 숫자를 재정렬합니다.

이러한 과정을 모든 자릿수에 대해 수행하면, 숫자들은 최종적으로 완전히 정렬된 상태가 됩니다.

아래는 C++에서 기수 정렬을 구현한 예시 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

void countSort(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) {
        countSort(arr, exp);
    }
}

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

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

    return 0;
}

이 코드는 기수 정렬을 구현하기 위해 countSort() 함수로 각 자릿수 별로 정렬하고, radixSort() 함수로 전체적으로 정렬하는 방식으로 동작합니다.

참고 문헌:

Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein