Radix Sort

1. Radix Sort란?

Radix Sort는 각 자릿수를 비교하여 수를 정렬하는 알고리즘이다.
숫자를 비교하는 것이 아니라, 자릿수별로 그룹화하여 정렬하는 방식이 특징이다.

다음 그림을 보면 처음에 배열에 저장된 값들이 맨 마지막에 오름차순으로 정렬됨을 알 수 있다.

정렬 과정
1. 가장 낮은 자리(일의 자리)부터 정렬: 각 숫자의 일의 자리 값을 기준으로 그룹을 나누고 정렬한다.
2. 다음 자리(십의 자리) 정렬: 정렬된 리스트를 기준으로 십의 자리 값을 비교하여 정렬한다.
3. 최상위 자리까지 반복: 가장 큰 자리수를 기준으로 정렬이 완료될 때까지 반복한다.
4. 최종 정렬 완료: 모든 자리수를 정렬하면 오름차순으로 정렬된 결과가 완성된다.

2. 코드

#include <bits/stdc++.h>
using namespace std;

int arr[1000002];
int d = 3;
int dn[3];
int n = 13;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vector<int> vec[10];
	
	for(int i=0; i<n; i++)
		cin >> arr[i];
	
	dn[0] = 1;
	
	for(int i=1; i<d; i++) dn[i] = dn[i-1] * 10;
	for(int i=0; i<d; i++)
	{
		for(int j=0; j<10; j++) vec[j].clear();
		for(int j=0; j<n; j++)
		{
			int didx = (arr[j]/dn[i])%10;
			vec[didx].push_back(arr[j]);
		}
		int aidx =0;
		for(int j=0; j<10; j++)
		{
			for(auto a : vec[j]) arr[aidx++] = a;
		}
	}
	
	for(int i=0; i<n; i++) cout << arr[i] << ' ';
	
	return 0;
}

// 입력 결과
// 502 103 200 129 182 92 10 4 59 293 719 285 643

// 출력 결과
// 4 10 59 92 103 129 182 200 285 293 502 643 719 

3. 특징

1) 비교 정렬이 아님
Radix Sort는 숫자 크기를 직접 비교하는 대신 각 자릿수를 기준으로 정렬을 수행한다. 이를 통해 비교 기반 정렬보다 효율적으로 동작할 수 있다.

2) O(dN) 시간 복잡도

• d: 최대 자릿수
• N: 정렬할 데이터 개수
• 일반적으로 d가 log(N)에 가까운 값이므로 O(NlogN) 수준의 성능을 기대할 수 있다.

3) 정렬 가능한 데이터의 범위 제한

• 음수 정렬을 지원하지 않으므로 변환 과정을 거쳐야 한다.
• 고정된 자릿수를 갖는 숫자에 적합하다.

4. 마무리

Radix Sort는 특정한 조건(자릿수가 일정하고 비교 정렬이 필요 없는 경우)에서 매우 강력한 성능을 발휘하는 정렬 알고리즘이다. 그러나 추가적인 공간이 필요하고 일반적인 데이터에는 Quick Sort나 Merge Sort가 더 유리할 수 있다. 사용 목적에 맞춰 적절한 정렬 알고리즘을 선택하는 것이 중요하다.

Reference
[실전 알고리즘] 0x0F강 정렬II - BaaaaaaaarkingDog