[기초] C++ 알고리즘 : 기수 정렬 (Radix Sort)

---

 

기수 정렬은 데이터를 개별적인 "자릿수"를 기준으로 여러 차례에 걸쳐 정렬하는 비교가 아닌 정렬 방식입니다.

이 알고리즘은 숫자의 가장 낮은 자리수부터 시작하여 가장 높은 자릿수까지

각 자릿수에 따라 순차적으로 정렬을 수행합니다.

이 과정은 주로 카운팅 정렬을 이용하여 각 단계에서 진행됩니다.

 

---

#include <iostream>

// 배열에서의 최대값을 찾는 함수
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

// 기수 정렬을 위한 카운트 정렬 함수
void countSort(int arr[], int n, int exp) {
    int output[n]; // 결과를 저장할 임시 배열
    int count[10] = {0};

    // 현재 자릿수에 따른 카운트를 증가
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    
    // 카운트 배열을 변형하여 위치를 조정
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // 결과 배열을 구성
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 정렬된 결과를 원래 배열에 복사
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// 기수 정렬 함수
void radixSort(int arr[], int n) {
    // 최대값을 찾아 가장 큰 자릿수를 결정
    int max = getMax(arr, n);

    // 모든 자릿수에 대해 카운트 정렬을 수행
    for (int exp = 1; max / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

// 배열을 출력하는 함수
void print(int arr[], int n) {
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

// 메인 함수
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);

    std::cout << "정렬 전 배열: ";
    print(arr, n);

    radixSort(arr, n);

    std::cout << "정렬 후 배열: ";
    print(arr, n);
    
    return 0;
}

 

 

출력 결과

 

정렬 전 배열: 170 45 75 90 802 24 2 66 
정렬 후 배열: 2 24 45 66 75 90 170 802

 

 

위 코드에서는 기수 정렬을 수행하는 과정을 보여주며,

배열을 사용해 각 자릿수마다 카운팅 정렬을 통해 정렬을 수행하고 있습니다.

기수 정렬은 특히 숫자의 범위가 넓지 않을 때,

매우 빠르고 효율적인 정렬 방법 중 하나입니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀