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

기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이기에 시간 복잡도가 O(n)이다.

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

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

방법은 다음과 같다.

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

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

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

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

 

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

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

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

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

 

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

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

위의 경우라면 최댓값이 1247로 저장되어 있을 것이고, 이 때 1부터 10씩 곱해가다보면 1000일 때, 1247보다 작을 것이고 000에서 10을 곱한 10000일 때 1247 보다 크게 된다. 즉 우리는 1부터 10000보다 작을 때 까지 10씩 곱하면서 자릿수를 찾을 수 있다. ( for(int i = 1; i < 10000; i = i * 10) )

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

 

위의 파랑색으로 적은 것은 각 버킷 칸이고, 그 밑에 적힌 값들은 버킷에 해당되는 값들을 적은 것이다. 이 상태에서 다시 값들을 순차적으로 뺀다면 다음과 같이 배열이 정렬될 것이다.

 

이렇게 되면 배열이 정렬이 하나도 안된 것 같지만, 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 RadixSort()
{
	int radix = 1; // 최대 자릿수까지 계산을 하기 위한 변수
	
	while (1) // 최대 자릿수가 몇 자리인지 알아내기 위함
	{
		// maxValue는 입력과 동시에 구해놓은 배열에서의 최댓값
		if (radix >= maxValue)
			break;

		radix *= 10;
	}
	for (int i = 1; i < radix; i*=10) // 1의 자리부터 10씩 곱하면서 최대자릿수 까지 반복
	{
		for (int j = 0; j < MAX; j++) // 모든 배열을 다 탐색하면서
		{
			int k = (arr[j] < i) ? 0 : (arr[j] / i) % 10;
			q[k].push(arr[j]);
		}
		int idx = 0;

		for (int j = 0; j < 10; j++)
		{
			while (!q[j].empty())
			{
				// 하나씩 빼면서 배열에 다시 저장
				arr[idx++] = q[j].front();
				q[j].pop();
			}
		}
	}
}

시간 복잡도

시간복잡도는 O(N)이다. 일단 왜 O(N)이 나오는지 부터 알아보자. 우리는 최대자릿수 까지 N번 탐색을 한다. 즉, 10개의 값이 있고 최대자릿수가 3이라고 가정했을 때  일의 자릿수를 찾는 과정에서 = 10번 탐색  십의 자릿수를 찾는 과정에서 = 10번 탐색  백의 자릿수를 찾는 과정에서 = 10번 탐색  즉 3 x 10 번 탐색을 하게된다. 이를 식으로 써보면 K * N번 탐색을 하는 것이고 이를 빅오 표기법으로 나타내면 O(N)이 된다.  탐색 과정을 지금까지 쭉 읽어와서 알겠지만 이 정렬법에서 최악, 최선의 경우 같은건 존재하지 않지만 '버킷'이라는 작지 않은 용량의 추가적인 메모리 공간이 필요하기 때문에 굉장히 주의해야하고 기수정렬의 최대의 단점이라고 볼 수 있다. 굉장히 빠르지만 추가적인 메모리 공간이 필요하기도 하고  버킷에 담고 빼는 과정도 양이 많아진다면 결코 무시할 수 없을정도로 시간을 잡아먹기 때문이다. 추가적으로 기수정렬에서 자릿수를 찾는 과정을 비트연산법으로도 구현이 가능하다고 한다. 

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>	
#include <map>

using namespace std;
using ll = long long;

#define MAX 100

int arr[MAX];
int maxValue;
bool flag[10001];
queue<int> q[10];

void Print()
{
	cout << "####################################################################################################################" << endl;
	int cnt = 0;

	for (int i = 0; i < MAX; i++)
	{
		cout << arr[i] << ' ';

		if (++cnt == 20)
		{
			cnt = 0;
			cout << endl;
		}
	}
	cout << "####################################################################################################################" << endl;
	cout << endl;
}

void RadixSort()
{
	int radix = 1; // 최대 자릿수까지 계산을 하기 위한 변수

	while (1) // 최대 자릿수가 몇 자리인지 알아내기 위함
	{
		// maxValue는 입력과 동시에 구해놓은 배열에서의 최댓값
		if (radix >= maxValue)
			break;

		radix *= 10;
	}
	for (int i = 1; i < radix; i *= 10) // 1의 자리부터 10씩 곱하면서 최대자릿수 까지 반복
	{
		for (int j = 0; j < MAX; j++) // 모든 배열을 다 탐색하면서
		{
			int k = (arr[j] < i) ? 0 : (arr[j] / i) % 10;
			q[k].push(arr[j]);
		}
		int idx = 0;

		for (int j = 0; j < 10; j++)
		{
			while (!q[j].empty())
			{
				// 하나씩 빼면서 배열에 다시 저장
				arr[idx++] = q[j].front();
				q[j].pop();
			}
		}
	}
}

int main()
{
	srand((unsigned)time(NULL));
	int i = 0;

	do
	{
		arr[i] = (rand() % 10000) + 1;
		
		if (!flag[arr[i]])
		{
			flag[arr[i]] = true;

			if (maxValue < arr[i])
				maxValue = arr[i];

			i++;
		}
	} while (i < MAX);
	cout << "[ Initialize Array State ] " << endl;
	Print();
	RadixSort();
	cout << "[ After Sort Array State ] " << endl;
	Print();
}

 

[ 정렬 ] 기수 정렬 (Radix Sort) (C++) :: 얍문's Coding World.. (tistory.com)