기수정렬 (Radix sort)

숫자의 각 자리 수는 0~9로 이루어져있기 때문에 자리 수 별로 정리한다고 생각하면 쉽다

 

1. 우선 일의 자리를 기준으로 해당하는 위치에 배열 후 정렬

2. 그다음 10의 자리 수를 기준으로 정렬

3. 위 과정을 반복하며 최고 자리수까지 정렬하면 된다.

 

위 그림을 보면 알수 있듯이 먼저들어온 수가 먼저 나가기 때문  queue자료구조를 사용하여 구현해 볼 것이다. 주의 해야할 점은 최대 자리수 보다 작은 자릿수 즉 최대자릿수가 1000일때 1~999 같은 세자리 수는 앞에 자리수를 0으로 계산해 줘야한다.

#include <iostream>
#include <vector>
#include <math.h>
#include <time.h>
#include <queue>

using namespace std;

int arr[20];
queue<int> que[10];
void radixSort(int* arr,int size, int maxValue) {
	int maxLen = 1; // maxValue 의 자릿수 == 최대값의 자릿수를 구한다
	while (maxValue / 10 != 0) {
		maxValue /= 10;
		maxLen *= 10;
	}

	for (int i = 1; i <= maxLen; i *= 10) {
		for (int j = 0; j < size; j++) {
			int k = 0; // 자릿수
			if (arr[j] >= i) {
				k = (arr[j] / i) % 10;
			}
			que[k].push(arr[j]);
		}
		int idx = 0;
		for (int j = 0; j < 10; j++) {

			while (!que[j].empty()) {
				arr[idx] = que[j].front();
				que[j].pop();
				idx++;
			}
		}
	}
	
	
}

int main(){
	srand(time(0));
	int max = 0;
	for (int i = 0; i < 20; i++) {
		arr[i] = rand() % 1000;
		if (max < arr[i]) max = arr[i];
	}
	cout << "### Before Sorting ###" << endl;
	for (int i = 0; i < 20; i++) {
		cout << arr[i] << " ";
	}

	cout << endl;
	radixSort(arr, 20, max);
	cout << "### After Sroting ###" << endl;
	for (int i = 0; i < 20; i++) {
		cout << arr[i] << " ";
	}

	

}

 

시간 복잡도를 생각해보면  n개의 입력에 대해서 최대 자리수 m만큼의 연산이 필요하다 

즉, O(n*m)으로 O(n)의 빠른 시간복잡도를 가지지만 단점으로는 queue에 자릿수에 따라 숫자를 저장해둘 공간이 필요하므로 size가 느러남에 따라 메모리 공간을 차지하게 되는 단점이 있다.