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

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

 

기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.

공간을 나눠 알맞은 데이터를 놓는 방법이 버킷 정렬 (Bucket Sort)과 비슷하다.

* 버킷 소트(bucket sort)는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다.

 

특징

• 데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식이다.
• 비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘이다. 
• 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다.
• 전체 데이터의 기수를 위한 버킷이라는 추가적인 메모리 공간이 필요하다. 
  • 10 진수인 데이터들을 정렬하기 위해서는 0~9 를 저장할 10개의 공간이 필요하지만, 만약 알파벳을 정렬한다면 총 길이가 26인 버킷이 필요하다.
• 시간 복잡도는 O(dn)이다. (d = 최대 자리 수) (n = 데이터의 개수)
• 정렬 이후에도 중복된 값들은 자리가 뒤바뀌지 않는 안정정렬에 속한다.
• 가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit), 가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Digit)라고 불린다.
• LSD 방식의 경우 키의 수를 n, 버켓의 종류 수를 k라고 했을 때, 공간복잡도는 O(n+k) 이다.
• MSD 방식의 경우 키의 수를 n, 버켓의 종류 수를 k, 키의 최대 길이를 d라고 했을 때, 공간복잡도는 O(n+d∗k) 이다.
• MSD  방식은 LSD와 비교했을 때 정렬 상태 확인등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다
• 정렬 대상의 모든 길이가 동일해야 가장 효율적이다.

 

기수 정렬의 작동을 간소하게 보여준다.

위 이미지 처럼 가장 낮은 자리수 부터 비교 하는 방법을 LSD(Least-Significant-Digit) 라고 한다.

가장 낮은 자리수 부터 점차 자리수를 높여가며 정렬한다.

같은 자리수의 모임들은 일반적으로 Queue구조로 저장을 하며, 이는 정렬 과정에서 자리가 뒤바뀌지 않게 하기 위함이다.

자리 값을 위한 Queue 구조

정렬되지 않은 수 { 0123, 2154, 0222, 0004, 0283, 1560, 1061, 2150 } 가 있을 때, 기수 정렬을 이용하여 정렬하는 방법은 다음과 같다.

 

1. 먼저 기수 정렬을 위한 공간(버킷)을 마련한다.

     ( 10 진수인 데이터들을 정렬하기 위해서는 0~9 를 저장할 10개의 공간이 필요)

2. 가장 앞에 있는 원소 부터 마지막 원소까지 자리수를 보고 Queue에 저장한다(push_back)

3. 마지막 원소까지 각 Queue에 저장이 완료되면, 첫번째 Queue부터 순서대로 비워준다.

     Queue는 먼저 입력된 데이터가 먼저 출력될 수 있는 구조를 가졌다. FIFO 구조

     (Queue 0에 담겨있는 1560과 2150 중 먼저 들어온 1560을 먼저 꺼낸다.)

 

4. 자리수를 옮겨가며 같은 방식으로 Queue에 입력하고 출력을 반복한다.

5. 마지막 자리수까지 정렬이 되면 완료

 

 

#include <iostream>
#include <queue>

using namespace std;

queue<int> digitQueue[10];

void Radix_Sort(int arr[], int n);

int main()
{
    int arr[] = {123, 2154, 222, 4, 283, 1560, 1061, 2150};
    int length = sizeof(arr) / sizeof(int);
    Radix_Sort(arr, length);

    // 결과 확인
    for (int i = 0; i < length; i++)
    {
        cout << arr[i] << ",";
    }

}
// 기수정렬 함수 !
void Radix_Sort(int arr[], int n)                
{
    int maxValue = 0;
    int radix = 1;
    // 배열 속 최대 값 찾기
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    // 최대 자릿수가 몇 자리인지 알아내기 위한 반복문 !
    while (true)                    
    {
        if (radix >= maxValue) break;
        radix = radix * 10;
    }
    // 1의 자리부터 10씩 곱하면서 최대자릿수 까지 반복 !
    for (int i = 1; i < radix; i = i * 10)   
    {
        // 모든 배열을 탐색
        for (int j = 0; j < n; j++)    
        {
            int k = (arr[j] / i) % 10;      // 자리값 추출
            digitQueue[k].push(arr[j]);     // Queue배열에 해당 값을 순차적으로 저장
        }

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