[ 정렬 ] 기수 정렬 (Radix Sort) (C++)

이번 글에서는 기수정렬(Radix Sort)에 대해서 다뤄보겠다.

기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이다.

버블, 선택, 퀵, 힙, 병합, 삽입, 셸 정렬은 아무리 빨라봤자 NlogN 의 시간복잡도를 갖는다.

즉, 왠만큼 빠르게 비교해본다고 해도 정렬에서 저정도의 시간은 걸린다고 볼 수 있다. 하지만, 기수정렬은 O(N) 이라는 말도 안되는 시간복잡도를 갖는다. 왜냐하면 비교를 하지 않기 때문이다 ! 그러면 무조건 기수정렬이 제일 좋겠네? 라고 생각할 수 있지만

이 질문에 대한 답은 제일 밑에서 알아보도록 하자.

구체적인 정렬 법을 알기 전에 이름인 '기수'가 뭔지 부터 알아보자. 여기서 '기수'라는 것은 '자릿수'를 의미한다.

자릿수로 뭘 어떻게 하는 것일까??

방법은 다음과 같다.

1. 1의 자릿수를 보면서 각각의 버킷에 알맞게 담아준다. 버킷에서 순차적으로 뺀다면 1의 자릿수에 맞게 정렬이된다.

2. 1)에 의해서 정렬된 배열에서, 10의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다.

3. 2)에 의해서 정렬된 배열에서, 100의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다.

4. 최대 자릿수까지 계속해서 반복한다..

이게 끝이다. 그런데 위에서 갑자기 '버킷'이라는 새로운 개념이 등장한다.

여기서는 그냥 '뭐 숫자에 알맞게 새로운 공간에 값을 임시적으로 저장해주는 방식이구나!' 정도만 알고가자.

구체적인 과정을 알아보자.

먼저 최대자릿수 까지 위의 과정을 반복해야 하므로 우리는 최대자릿수가 몇 자리 숫자인지를 알아야 한다.

예를 들어서 배열이 { 1, 100 , 1000 } 이 있다면 최대 자릿수는 4자리가 된다.

그렇다면 다음과 같은 배열이 있다고 생각해보자.

먼저 최대자릿수를 찾아보면 '4'자리 라는 것을 알 수 있다.

최대 자릿수를 찾는 방법은 간단하다. 배열을 입력 받을 때 최댓값을 저장해 놓고, 1부터 10씩 곱해가면서 최댓값과 비교를 해서

더 크거나 같을 때 까지 반복하면 된다.

위의 경우라면 최댓값이 1247로 저장되어 있을 것이고, 이 때 1부터 10씩 곱해가다보면 1000일 때, 1247보다 작을 것이고

1000에서 10을 곱한 10000일 때 1247 보다 크게 된다. 즉 우리는 1부터 10000보다 작을 때 까지 10씩 곱하면서 자릿수를 찾을

수 있다. ( for(int i = 1; i < 10000; i = i * 10) )

그렇다면 위의 배열에서 1의 자리 숫자들을 보면서 새로운 버킷에 한번 담아보도록 하자. 여기서 버킷은 총 10개가 존재한다.

왜냐하면 0 ~ 9에 대한 버킷이다. 즉, 1의 자리가 0인 놈은 0번 버킷에, 1의 자리가 1인 놈은 1번버킷에... 이런 식으로 담기게된다.

이렇게 되면 다음과 같이 될 것이다.

위의 파랑색으로 적은 것은 각 버킷 칸이고, 그 밑에 적힌 값들은 버킷에 해당되는 값들을 적어본 것이다.

즉 0번 버킷이 여기서 의미하는 것은 1의자리 숫자가 0인 놈들은 여기로 오세요 를 의미하고

1번 버킷은 1의자리 숫자가 1인 놈들은 여기로 오세요 를 의미한다.

즉, 위와 같이 버킷에 담아질 것이고 이 상태에서 다시 값들을 순차적으로 뺀다면 다음과 같이 배열이 정렬될 것이다.

이렇게 되면 배열이 정렬이 하나도 안된 것 같지만, 1의자리만 본다면 오름차순으로 정렬되있음을 확인할 수 있다.

그 다음과정은 ? 이 배열에서 10의 자리를 비교해서 또 버킷에 담아주면 된다.

위의 상태는 10의 자리를 비교했을 때 각 자릿수에 숫자들을 알맞게 버킷에 담은 것이다.

이 때, 일의자리 숫자인 '2'같은 경우에는 '02'로 보고 10의 자리 숫자가 0인 곳에 들어가게 된다.

또 이 버킷을 0부터 9까지 순차적으로 돌면서 값을 순차적으로 빼내보면 배열이 다음과 같이 정렬될 것이다.

또 얼핏보면 정렬이 하나도 안된 것 같아 보이지만, 십의자리에만 집중을하고 배열을 보면 십의 자리가 오름차순으로

정렬되어 있음을 확인할 수 있다.

이제 백의 자리에 대해서 버킷에 담아보겠다.

순차적으로 빼내보면

점점 정렬이 되는 것 같다. 

이제 천의자리에 대해서 버킷에 담아보자.

순차적으로 빼내보면

와 같아진다. 정렬이 완성되었다는 걸 볼 수 있다 !

기수정렬은 이렇게 값들간의 실제적인 비교는 없지만 각 숫자들의 '기수' 만으로 정렬을 하는 방식이다.

그렇다면 여기서 위에서 말했던 '버킷'에 대해서 알아보자.

기수정렬은 '버킷'이라는 추가적인 공간할당이 필요하다. 가장 일반적으로 사용되는 것이 Queue이다.

왜냐하면 Queue는 FIFO 구조로써 먼저 들어간 값이 먼저 나오기 때문에, 들어간 그대로 빼내주기만 하면 그것이 순차적으로

꺼내는 것과 동일한 역할을 하기 때문이다.

본인은 버킷의 역할을 하는 Queue를 10칸짜리 배열로 만들어주었다.

그래서 자릿수를 구할 때 마다 Queue의 적절한 Index에 push해주었다. 이 부분은 밑에서 코드를 본 후에 더욱 더 구체적으로

알아보자.

이번에는 핵심이라고 볼 수 있는 '자릿수에 있는 값'을 구하는 법을 알아보자.

예를들어서 123이라는 값이 있다. 우리는 일의자릿수를 구한다고 치면 아마 '3'이라는 결과를 얻어내야 한다.

그렇다면 어떻게 해야될까?? 바로 123을 10으로 모듈러(%) 연산을 하면 된다.

123 % 10 = 3 이기 때문에 손쉽게 구해낼 수 있다.

그렇다면 123에서 십의자릿수를 구해보자. 십의자릿수라면 '2'라는 결과를 얻어내야 한다.

일의 자릿수와 똑같이 123 % 10을 하면, 3이 나오게 된다...

그러면.. 12를 10으로 모듈러 연산을 하게 되면 어떻게 될까? '2'라는 값을 얻어낼 수 있다.

그렇다면 123을 12로 어떻게 만들까?? 123을 10으로 나눠버리면된다. 123 / 10 = 12 이고 이를 10으로 모듈러 연산을 하게 되면

'2'라는 값을 얻어낼 수 있다.

마지막으로 123에서 백의 자리를 얻어내는 과정을 한번 해보자.

123을 십의 자리와 마찬가지로 10으로 나눈 후에 %10을 하게되면 2라는 값을 얻게 된다.

그럼 123을 100으로 나눈 후에 %10을 하게되면? 123 / 100 = 1 이고 1 % 10 = 1 로 '1'의 값을 얻게 된다.

위의 과정을 깔끔하게 식으로 나타낸다면???

얻어 내고자 하는 값 = (원래의 값 / 얻어 내고자 하는 자릿수) % 10 으로 표현할 수 있다.

그렇다면 코드를 한번 보면서 정리해보자.

void Radix_Sort()                // 기수정렬 함수 !
{
    int Radix = 1;                // 최대 자릿수까지 계산을 하기 위한 변수
    while (1)                    // 최대 자릿수가 몇 자리인지 알아내기 위한 반복문 !
    {
        if (Radix >= Max_Value) break;    // Max_Value는 입력과 동시에 구해놓은 배열에서의 최댓값 !
        Radix = Radix * 10;        
    }
    for (int i = 1; i < Radix; i = i * 10)    // 1의 자리부터 10씩 곱하면서 최대자릿수 까지 반복 !
    {
        for (int j = 0; j < MAX; j++)    // 모든 배열을 다 탐색하면서
        {
            int K;
            if (Arr[j] < i) K = 0;        // 만약 현재 배열의 값이 현재 찾는 자릿수보다 작으면 0 !
            else K = (Arr[j] / i) % 10;    // 그게 아니라면 위에서 말한 공식 적용 !
            Q[K].push(Arr[j]);        // Queue배열에 해당 값을 순차적으로 저장 !
        }

        int Idx = 0;
        for (int j = 0; j < 10; j++)    // 0부터 9까지 Queue에 저장된 값들을 순차적으로 빼내기 위한 반복문.
        {
            while (Q[j].empty() == 0)    // 해당 Index번호의 Queue가 빌 때 까지 반복
            {
                Arr[Idx] = Q[j].front();    // 하나씩 빼면서 배열에 다시 저장.
                Q[j].pop();        
                Idx++;
            }
        }
    }
}

# 시간복잡도

- 위에서도 간략이 말했지만 시간복잡도는 O(N)이다. 말도안되게 빠른 정렬 방법이라고 볼 수 있다.

  최악의 경우 최선의 경우 같은것도 존재하는 정렬법으로 굉장히 빠른 정렬법이다.

  일단 왜 O(N)이 나오는지 부터 알아보자.

  우리는 최대자릿수 까지 N번 탐색을 한다.

  즉, 10개의 값이 있고 최대자릿수가 3이라고 가정했을 때

  일의 자릿수를 찾는 과정에서 = 10번 탐색

  십의 자릿수를 찾는 과정에서 = 10번 탐색

  백의 자릿수를 찾는 과정에서 = 10번 탐색

  즉 3 x 10 번 탐색을 하게된다. 이를 식으로 써보면 K * N번 탐색을 하는 것이고 이를 빅오 표기법으로 나타내면 O(N)이 된다.

  탐색 과정을 지금까지 쭉 읽어와서 알겠지만 이 정렬법에서 최악, 최선의 경우 같은건 존재하지 않는다.

 

  하지만 ! 우리가 굉장히 주의해야할 것이 하나 있다. 이 정렬법이 제일 좋다고 생각할 수도 있지만 절대 그렇지 않다.

  왜냐하면, '버킷'이라는 작지 않은 용량의 추가적인 메모리 공간이 필요하기 때문이다.

  이것이 기수정렬의 최대의 단점이라고 볼 수 있다. 시간이 굉장히 빠르지만 추가적인 메모리 공간이 필요하기도 하고

  버킷에 담고 빼는 과정도 양이 많아진다면 결코 무시할 수 없을정도로 시간을 잡아먹기 때문이다.

 

  추가적으로 기수정렬에서 자릿수를 찾는 과정을 비트연산법으로도 구현이 가능하다고 한다. 본인은 비트연산에 대해서

  깊게 이해하지 못해서 아직까지 구현하지는 못하지만 이러한 방법이 있다는 것도 알아두자 !

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
 
#define MAX 100
using namespace std;
 
int Max_Value;
int Arr[MAX];
bool Flag[10001];
queue<int> Q[10];
 
void Print()
{
    cout << "####################################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%6d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "####################################################################################################################" << endl;
    cout << endl;
}
 
void Radix_Sort()
{
    int Radix = 1;
    while (1)
    {
        if (Radix >= Max_Value) break;
        Radix = Radix * 10;
    }
    for (int i = 1; i < Radix; i = i * 10)
    {
        for (int j = 0; j < MAX; j++)
        {
            int K;
            if (Arr[j] < i) K = 0;
            else K = (Arr[j] / i) % 10;
            Q[K].push(Arr[j]);
        }
 
        int Idx = 0;
        for (int j = 0; j < 10; j++)
        {
            while (Q[j].empty() == 0)
            {
                Arr[Idx] = Q[j].front();
                Q[j].pop();
                Idx++;
            }
        }
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < MAX; )
    {
        Arr[i] = (rand() % 10000) + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            if (Max_Value < Arr[i]) Max_Value = Arr[i];
 
            i++;
        }
    }
    
    cout << "[ Initialize Array State ] " << endl;
    Print();
    Radix_Sort();
    cout << "[ After Sort Array State ] " << endl;
    Print();
 
    return 0;
}