기수 정렬(Radix Sort)

개념 요약

• 비교 없이 수행하는 정렬 알고리즘이다.
• 기수로는 정수, 낱말 등 다양한 자료로 사용 가능하지만 크기가 유한하며 사전 순으로 정렬할 수 있어야 한다.
• 기수에 따라 원소를 버킷에 집어넣기 때문에 비교 연산이 없다.
• 정수 같은 자료의 정렬 속도가 매우 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만 한 메모리가 필요하다.
• 부동소수점 실수처럼 특수한 비교 연산이 필요한 경우엔 사용하지 못한다.
• MSD(최상위 유효숫자)와 LSD(최하위 유효숫자) 방식이 있다.
• MSD
  • 문자열이나 고정 길이 정수 표현 정렬에 전합니다.
  • 가장 큰 자릿수부터 정렬을 진행한다.
  • 중간에 정렬이 완료될 수 있다는 장점이 있지만 추가 작업이 필요하다.
• LSD
  • 가장 작은 자릿수부터 정렬을 진행한다.
  • MSD에 비해 간결하다.

---

정렬 과정

정수를 예로 과정 설명을 진행한다.

1. 특정 자릿수가 정렬된 결과를 넣을 큐 A(0~9), 정렬된 결과를 넣을 임시 큐 B(0~9)을 선언한다.
2. 원소를 차례대로 꺼내서 i번째 자리를 정렬하여 A에 넣는다.
3. A에서 원소를 차례대로 꺼내서 i번째 자리를 정렬하여 B에 넣는다.( i = 1, i < 최대 자릿수)
4. B에서 원소를 차례대로 꺼내서 A에 넣는다.
5. 3~4를 반복한다.
6. B에서 차례대로 원소를 꺼내서 원래 벡터에 초기화시킨다.

 

---

코드

int	get_digit_num(int num, int i)
{
	int	d = std::pow(10, i);
	return ((num / d) % 10);
}

int	get_max_count(int max_elem)
{
	int	count = 0;
	while (max_elem)
	{
		max_elem /= 10;
		++count;
	}
	return (count);
}

void	radix_sort(std::vector<int> &unsorted_array)
{
	std::vector<std::queue<int>>	A(10);
	int	max_elem = unsorted_array[0];

	// 최댓값 구하기, 1의 자리 정렬해서 A에 넣기
	for (int &elem : unsorted_array)
	{
		max_elem = (max_elem < elem ? elem : max_elem);
		A[elem % 10].push(elem);
	}
	// 원래 벡터 초기화
	unsorted_array.clear();
	int	temp = max_elem, count = get_max_count(max_elem);
	// 1(10의 자리)부터 시작해서 최대 자릿수까지 진행
	for (int idx = 1; idx < count; ++idx)
	{
		// 임시로 저장할 queue 생성
		std::vector<std::queue<int>>	B(10);
		// 0~9까지 해당하는 큐 불러오기
		for (int i = 0; i < 10; ++i)
		{
			// 해당 인덱스의 큐가 빌때까지 루프
			while (A[i].empty() == false)
			{
				// 가장 앞의 원소를 자릿수 구분하여 넣어주기
				int	num = A[i].front();
				B[get_digit_num(num, idx)].push(num);
				A[i].pop();
			}
		}
		// 기존 queue 초기화
		A.clear();
		// B를 그대로 A로 옮김
		for (int i = 0; i < 10; ++i)
			A.push_back(B[i]);
	}
	// 정렬이 완료된 큐벡터를 기존 벡터의 주소에 push
	for (int idx = 0; idx < 10; ++idx)
	{
		while (A[idx].empty() == false)
		{
			unsorted_array.push_back(A[idx].front());
			A[idx].pop();
		}
	}
}

---

시간 복잡도

• $O(d * n)$
  • d는 정렬한 자릿수

 

---

장단점

• 문자열, 정수 정렬 가능하다.
• 자릿수가 없는 것은 정렬할 수 없고 중간결과를 저장할 메모리 공간이 필요하다.