[c++] 기수 정렬(Radix Sort) 알고리즘

08 Dec 2023

기수 정렬(Radix Sort)은 비교 기반 정렬 알고리즘이 아닌, 자릿수를 기준으로 정렬하는 안정 정렬 알고리즘입니다. 이 알고리즘은 입력의 비트나 자릿수를 활용하여 정렬합니다. 계수 정렬(Counting Sort)이나 버킷 정렬(Bucket Sort)과 함께 기수 정렬은 선형 시간 복잡도 O(n)로 빠른 속도로 정렬할 수 있는 장점이 있습니다.

알고리즘 원리

기수 정렬은 가장 낮은 자리수부터 가장 높은 자리수까지 순차적으로 정렬하는 알고리즘이며, 각 자릿수마다 계수 정렬을 사용합니다. 가장 작은 자릿수부터 큰 자릿수순으로 정렬해 나가므로 중간 정렬 과정에서 크기가 큰 숫자일수록 비교 연산을 하는 횟수가 줄어들어 효율적인 정렬을 할 수 있습니다.

예시 코드

#include <iostream>
using namespace std;

// 기수 정렬을 위한 계수 정렬 함수
void countingSort(int arr[], int n, int exp) {
    int output[n]; // 정렬된 결과를 저장할 배열
    int count[10] = {0}; // 각 자릿수별 빈도수를 저장할 배열

    // 각 자릿수의 빈도수를 count 배열에 저장
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // count 배열 업데이트
    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_value = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }

    // 가장 큰 수의 자릿수까지 정렬을 수행
    for (int exp = 1; max_value / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

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

    radixSort(arr, n);

    cout << "기수 정렬 결과:" << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

시간 복잡도

기수 정렬의 시간 복잡도는 O(d*(n+k))입니다. 여기서 d는 가장 큰 수의 자릿수이고, k는 기수(예를 들어, 10진수 일 경우 k=10)입니다.

기수 정렬은 안정적인 정렬 방법으로, 입력 데이터에 음수가 포함되어도 잘 작동합니다.

기수 정렬은 정수를 정렬하는데 주로 사용되며, 비교 기반의 정렬 알고리즘과는 달리 정렬할 수 있는 데이터의 범위가 제한되어 있기 때문에 특정한 상황에서 유용하게 활용될 수 있습니다.

알고리즘 원리

예시 코드

시간 복잡도

참고 자료