[알고리즘] Radix Sort (기수정렬) 이란? (C++로 구현하기)

기수정렬이란?

기수정렬은 영어로 'Radix Sort' 이다.

여기에서 'Radix'가 의미하는 바는 각 자리를 이루고 있는 숫자들을 말한다.

즉, 각각의 수의 자릿수를 대상으로 정렬한다는 것이다.

 

기수정렬을 다른 정렬들(버블정렬, 퀵정렬 등) 과는 다른 특성이 있다.

첫 번째는 비교가 이루어지지 않는 정렬이라는 것이고,

두 번째는 정렬의 이론상 한계인 O(N * log N)을 뛰어넘는 O(N)이라는 것이다.

 

이렇게만 보면 어떤 정렬보다 좋을 것 같지만

실제로는 생각보다 많이 쓰이지않는데, 이는 적용 범위가 한정적이기 때문이다.

반대로 말하면, 최적의 상황에서 사용하면 최적의 효율을 보여준다는 것이기도 하다.

(실제로, 알고리즘 풀이 중에서는 쓰이는 경우가 간간히 있다.)

 

 

동작 원리

다음과 같은 배열을 정렬한다고 가정해보자.

 

정렬을 원하는 배열

기수정렬에는 각 자릿수를 담고 있을 버킷(Bucket) 이라는 공간이 필요하다.

다음과 같이 생겼다고 가정해보자.

 

버킷 (Bucket) 의 예시

이 공간에서 숫자들의 각 자릿수를 비교해서 맞는 위치에 넣었다가 빼는 과정을 거친다.

이 넣었다가 빼는 과정을 선입선출로 구현하면,

적어도 각 자릿수에 대해서는 정렬된 결과가 나오게 된다.

선입선출로 구현이 필요하기 때문에, 각 버킷은 Queue로 구현한다.

 

가장 먼저, 1의 자릿수부터 진행해보자.

배열의 각 원소에 대해서 1의 자릿수를 비교해서 버킷에 삽입하면 다음과 같이 만들어진다.

 

 

그리고 이 버킷에서 왼쪽부터 오른쪽으로 모든 값들을 빼서 배열에 넣으면 다음과 같다.

 

 

1의 자릿수대로 정렬된 것을 확인할 수 있다.

이러한 과정을 각 자릿수에 반복하면 최종적으로 다음과 같이 정렬이 완성된다.

 

 

 

 

구현 (C++)

#include <iostream>
#include <cstdlib>
#include <ctime>

#define MAX_QUEUE	101
#define ARR_SIZE	20

using namespace std;

template<typename T>
class Queue {
public:
	T arr[MAX_QUEUE];
	int f = 0, r = 0;

	T front() { return arr[f]; }
	bool isEmpty() { return (f == r); }
	bool isFull() { return ((r + 1) % MAX_QUEUE == f); }
	int size() { return (f > r ? f - r : r - f); }
	void enqueue(T element)
	{
		arr[r++] = element;
		r %= MAX_QUEUE;
	}
	void dequeue() { f = (f + 1) % MAX_QUEUE; }
};

int get_digit(int n, int digit)
{
	int div = 1;
	for (int i = 0; i < digit; i++) div *= 10;

	n /= div;
	return (n % 10);
}

void radix_sort(int *arr, int size)
{
	Queue<int> q[10];

	int maxNum = 0, maxDigits = 0;
	for (int i = 0; i < size; i++) if (maxNum < arr[i]) maxNum = arr[i];
	while (maxNum != 0)
	{
		maxDigits++;
		maxNum /= 10;
	}

	for (int i = 1; i <= maxDigits; i++)
	{
		for (int j = 0; j < size; j++) q[get_digit(arr[j], i)].enqueue(arr[j]);
		int arrIdx = 0;
		for (int j = 0; j < 10; j++)
		{
			while (!q[j].isEmpty())
			{
				arr[arrIdx++] = q[j].front();
				q[j].dequeue();
			}
		}
	}
}

int main(void)
{
	int arr[ARR_SIZE];

	srand(time(NULL));
	for (int i = 0; i < ARR_SIZE; i++) arr[i] = (rand() % 100000) + 1;

	cout << "Before Radix sort\n";
	for (int i = 0; i < ARR_SIZE; i++) cout << arr[i] << " ";
	cout << "\n\n";

	radix_sort(arr, ARR_SIZE);

	cout << "After Radix sort\n";
	for (int i = 0; i < ARR_SIZE; i++) cout << arr[i] << " ";
	cout << "\n";

	return 0;
}