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

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

기수 정렬(Radix Sort)은 정수들의 정렬을 위해 사용하는 알고리즘 중 하나입니다. 비교 기반의 정렬 알고리즘이 아니라, 각 숫자의 자리수를 기준으로 정렬을 수행하는 방식을 사용합니다. 

 

기수 정렬의 시간 복잡도는 O(NK)입니다. 여기서 N은 정렬할 숫자의 개수, K는 숫자의 최대 자리수입니다. 따라서 데이터의 개수가 많고, 숫자의 범위가 클 경우에는 다른 정렬 알고리즘에 비해 빠른 성능을 보여줍니다.

하지만 기수 정렬은 특정 조건을 만족하는 정수에 대해서만 사용할 수 있으며, 부동소수점 수나 문자열 등에는 적용이 어렵다는 단점이 있습니다. 또한, 추가적인 메모리 공간을 필요로 하는 알고리즘이므로 메모리 사용에 제약이 있는 경우 사용하기 어렵습니다.

 

기수정렬(Radix Sort) 코드

// 최대값 찾기
int getMax(vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

// 기수 정렬 함수
void radixsort(vector<int>& arr) {
    int maxVal = getMax(arr); // 최대값 찾기

    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> output(arr.size());
        int count[10] = {0};

        // 현재 자릿수(exp)에 대한 카운트 계산
        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];
    }
}

 

 

기수정렬(Radix Sort) 과정

 

기수 정렬은 다음과 같은 과정으로 수행됩니다:

1. 최대값 찾기: `getMax` 함수는 주어진 배열에서 가장 큰 값을 찾아 반환합니다. 이 값은 가장 큰 자릿수를 가진 숫자를 찾는데 사용됩니다.

2. 기수 정렬: `radixsort` 함수는 주어진 배열을 정렬하는 주요 함수입니다. 이 함수는 가장 큰 자릿수를 찾아서 그만큼의 라운드를 돌며 정렬을 수행합니다. 각 라운드에서는 현재 자릿수를 기반으로 카운트를 계산하고, 이를 기반으로 출력 배열을 생성합니다.

3. 카운트 계산: 각 숫자를 현재 자릿수로 나눈 후 10으로 나눈 나머지를 인덱스로 사용하여 카운트 배열의 값을 증가시킵니다. 이렇게 하면 각 자릿수에 해당하는 숫자의 개수를 카운트할 수 있습니다.

4. 카운트 배열을 누적합으로 변경: 카운트 배열의 각 요소를 이전 요소와 더하여 누적합으로 변경합니다. 이렇게 하면 각 요소의 값이 해당 숫자 이하의 숫자의 개수가 됩니다.

5. 출력 배열 생성: 원래 배열의 숫자를 뒤에서부터 보면서 해당 숫자의 자릿수를 인덱스로 사용하여 카운트 배열의 값을 찾고, 이 값을 인덱스로 사용하여 출력 배열에 숫자를 넣습니다. 이후 해당 카운트 배열의 값을 감소시킵니다.

6. 원래 배열에 복사: 출력 배열의 값을 원래 배열에 복사하여 원래 배열을 정렬합니다.

7. 다음 자릿수로 이동: 현재 자릿수에 10을 곱하여 다음 자릿수로 이동합니다. 이 작업을 가장 큰 자릿수만큼 반복하여 모든 자릿수에 대해 정렬을 수행합니다.

최종적으로 이 코드는 주어진 배열을 기수 정렬하여 출력합니다. 이 과정을 통해 각 숫자의 자릿수를 기준으로 정렬된 배열을 얻을 수 있습니다.

테스트 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 최대값 찾기
int getMax(vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

// 기수 정렬 함수
void radixsort(vector<int>& arr) {
    int maxVal = getMax(arr); // 최대값 찾기

    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> output(arr.size());
        int count[10] = {0};

        // 현재 자릿수(exp)에 대한 카운트 계산
        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];
    }
}

// 메인 함수
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;
}

테스트 결과

2 24 45 66 75 90 170 802