[CS] 기수 정렬(Radix Sort)

기수정렬(radix sort) 알고리즘의 개념

• 기수정렬은 낮은 자리수부터 비교하여 정렬하는 알고리즘.
• 비교 연산은 하지 않으며 정렬 속도는 빠르지만 데이터 전체 크기에 기수(자릿수) 테이블의 크기만한 메모리가 더 필요함
• 시간 복잡도는 O(dn)
• 안정 정렬(stable sort)

과정 설명

1. 0~9 까지에 Bucket(Queue 자료구조)를 준비한다.

2. 입력 데이터에 대하여 가장 낮은 자리수부터 시작하여 해당하는 Bucket에 차례대로 데이터를 추가한다.

3. 0부터 차례대로 Bucket에서 데이터를 다시 가져와 입력 데이터에 삽입한다.

4. 입력 데이터의 가장 높은 자리수까지 2,3번 과정을 반복한다.

기수 정렬(Radix Sort) C++ 코드

#include<iostream>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
//양의 정수
void radix_sort(vector<int>& v){
	int max_v = *max_element(v.begin(), v.end()); //최대 값 추출
	int digit= (max_v ==0)? 0 : ((int)log10(max_v)) + 1; // 최대 값의 자릿수 추출
	queue<int> K[10]; // 0~9 까지의 Queue 생성
	int divisior = 1;
	for (int i = 0; i < digit; i++){ // 입력 데이터에 대하여 가장 낮은 자리수부터 시작하여 해당하는 Bucket에 차례대로 데이터를 추가
		for (int j = 0; j < v.size(); j++){
			int idx = (v[j] / divisior)%10; // 현재 자릿수에 해당하는 값만을 추출하여 인덱스로 변환  
			K[idx].push(v[j]); // Queue의 기수 테이블에 맞는 인덱스에 접근하여 입력 데이터 추가 
		}
		int idx = 0;
		for (int j = 0; j < 10; j++) { // 0부터 차례대로 버킷에서 데이터를 다시 가져와 입력 데이터에 삽입
			while (!K[j].empty()) {
				v[idx] = K[j].front();
				K[j].pop();
				idx++;
			}
		}
		divisior *=  10;
	}
}
int main()
{
	vector<int> v = { 10,412,345,100,23,149,23 };
	radix_sort(v);
	for (auto& e : v) {
		cout << e << endl;
	}
	return 0;
}

• 추후 기수 정렬 기반으로 양의 실수 정렬 코드도 올릴 예정.