정렬 (13) - 기수 정렬 (Radix Sort)

1. 알고리즘 개요

• Counting 정렬과 마찬가지로 $O(n)$의 속도로 굉장히 빠른 정렬방법.

• 비교(Comparison)을 하지 않고 자리수 큐에 데이터를 넣었다 뺐다 하면서 정렬함

• 양의 정수끼리 혹은 음의 정수끼리 등 제한적인 데이터만 정렬 가능 (실수에서는 불가)

• 아래 예시를 보면 자세한 동작을 알 수 있음.

 

1) 입력 배열

 

2) 1의 자리 : 1의 자리수에 맞춰서 큐에 입력하고 FIFO 순서대로 출력 (1의 자리 정렬)

 

3) 10의 자리수 : 10의 자리수에 맞춰서 큐에 입력하고 FIFO 순서대로 출력 (10의 자리 정렬)

 

3) 100의 자리수 : 100의 자리수에 맞춰서 큐에 입력하고 FIFO 순서대로 출력 (100의 자리 정렬)

 

4) 1000의 자리수 : 1000의 자리수에 맞춰서 큐에 입력하고 FIFO 순서대로 출력 (정렬 완료)

 

2. 소스코드

#include<stdio.h>
#include<queue>
using namespace std;

int get_max_radix(int *arr, int size){
	
	int max_val = 0;
	for(int i = 0 ; i < size ; i++){
		if(max_val < arr[i]){
			max_val = arr[i];
		}
	}
	
	int max_radix = 1;
	while(max_val / 10 > 0){
		max_val /= 10;
		max_radix *= 10;
	}
	
	return max_radix;
}

void radix_sort(int *arr, int size){
	int max_radix = get_max_radix(arr, size);
	
	queue<int> Q[10]; // Queue 10개 (1 ~ 9 자리)
	
	for(int i = 1 ; i <= max_radix ; i *= 10){
		for(int j = 0 ; j < size ; j++){
	
			int k = 0; 
			// 자리수 
					
			if(arr[j] >= i){ 
				k = (arr[j] / i) % 10;
				// (1, 10, 100)보다 크면 계산하고 
				// 작으면 0으로 처리함 
				// (e.g. 10의자리에서 2 -> 02 -> 0) 
			}
			
			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();
				idx++;
			}
		}
	} 
}

int main(){
	
	int arr[] = {1,3,2,4,1,23,126,213,12,12,3,12,3,23,23};	
	int size = sizeof(arr)/sizeof(arr[0]);
	radix_sort(arr, size);
	
	for(int i = 0 ; i < size ; i++){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

3. Reference 

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