기수 정렬

계수 정렬Counting Sort와 마찬가지로 비교를 하지 않아요.

데이터를 구성하는 요소의 기수Radix를 활용해서 정렬을 진행합니다. 정수를 정렬한다 가정하면 첫째 자리수를 기준으로 정렬 -> 둘째 자리수를 기준으로 정렬 -> ... 이렇게 반복해서 정렬을 하는 알고리즘이죠.

특징

시간 복잡도는 O(d * (n + b))이고, d는 정렬할 숫자의 자릿수, b는 10입니다(각 자릿수의 범위는 0~9니까요).

기수 정렬의 경우 문자열이나 정수는 정렬이 가능하지만, 자릿수가 없는 것은 정렬할 수가 없습니다(실수가 대표적이죠). 계수 정렬처럼 중간 결과를 저장할 배열이 필요해 In-place하지 않습니다.

소스

큐Queue 또는 계수 정렬Counting Sort를 활용할 수 있는데, 이번엔 계수 정렬Counting Sort를 활용해 구현해보도록 할게요.

#include <vector>
#include <limits.h>

using namespace std;

class RadixSort
{
public:
	static void sort(vector<int>& arr)
	{
		int maxValue = getMax(arr);

		for(int exp = 1; maxValue / exp > 0; exp *= 10)
			countingSort(arr, exp);
	}

private:
	static void countingSort(vector<int>& arr, int exp)
	{
		vector<int> buffer(arr.size());
		vector<int>	counting(10);

		for(int i = 0 ; i < arr.size(); ++i)
			counting[(arr[i] / exp) % 10]++;

		for(int i = 1 ; i < counting.size(); ++i)
			counting[i] += counting[i - 1];

		for(int i = arr.size() - 1; i >= 0 ; --i)
			buffer[--counting[(arr[i] / exp) % 10]] = arr[i];

		arr = buffer;
	}

	static int getMax(const vector<int>& arr)
	{
		int ret = INT_MIN;
		for(const int& a : arr)
		{
			if(ret < a)
				ret = a;
		}
		return ret;
	}
};

추가

위에 제가 구현한 코드는 LSDLeast-significant-digit 방식으로, 가장 낮은 자리수부터 전개를 합니다. 가장 높은 자리수부터 시작하는건 MSDMost-significant-digit라고 해요.

MSD의 경우 정렬을 수행하는 과정에서 이미 정렬이 완료되어, 끝까지 수행해야 하는 LSD보다 효율적이에요(ex. 10004와 70002의 비교).

하지만, 그럴려면 한번 기수 정렬을 수행하고 체크 처리를 해야하는데다, 구현은 LSD가 용이하기 때문에 주로 LSD가 언급이 됩니다.