[c++] 기수 분류기

12 Dec 2023

기수 분류기는 정수나 문자열을 정렬하는 알고리즘입니다. 이번에는 C++을 사용하여 기수 분류기를 구현해보겠습니다.

기수 분류 알고리즘

기수 분류 알고리즘은 숫자를 자릿수별로 비교하고 정렬하는 방식으로 동작합니다. 가장 낮은 자릿수부터 가장 높은 자릿수까지 순차적으로 정렬을 수행합니다.

예를 들어, 135, 246, 168, 247, 149 숫자들을 기수 분류 알고리즘을 사용하여 정렬하면 135, 149, 168, 246, 247 로 정렬될 것입니다.

#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 maxNumber = *max_element(arr.begin(), arr.end());

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

int main() {
    vector<int> arr = {135, 246, 168, 247, 149};
    radixSort(arr);

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

위의 코드는 C++을 사용하여 기수 분류 알고리즘을 구현한 예시입니다.

결론

이렇게 C++을 사용하여 기수 분류 알고리즘을 구현할 수 있습니다. 이 알고리즘은 특히 정수형 데이터를 효율적으로 정렬하는 데 사용됩니다.

기수 분류 알고리즘

결론

참고 자료