3-3 정렬(RadixSort)

기수 정렬은 값을 비교하지 않는 특이한 정렬이다.

기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.

기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 의미한다.

 

이미지 출처:https://devjin-blog.com/sort-algorithm-9/

 

기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표하는데 위의 그림의 값인 329, 457, 657, 839, 436, 720, 355들을 일의 자릿수 기준으로 배열 원소를 큐에 집어넣는다. 그런 다음 0번째 큐부터 9번째 큐까지 pop을 진행한다.

그 결과는 720, 355, 436, 457, 657, 329, 839가 만들어진다. 이어서 십의 자릿수를 기준으로 같은 과정을 진행하고 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void radixSort(vector<int>&);
int main() {
	cin.tie(0)->sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> arr(N, 0);
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}

	radixSort(arr);
	for (auto& it : arr) {
		cout << it << '\n';
	}
	return 0;
}

void radixSort(vector<int>& arr) {
	queue<int> q[10];
	int radix = 1;

	for (int i = 0; i < arr.size(); ++i) {
		if (radix <= arr[i])
			radix *= 10;
	}

	for (int i = 1; i < radix; i *= 10) {
		for (int j = 0; j < arr.size(); ++j) {
			int num = (arr[j] / i) % 10;
			q[num].push(arr[j]);
		}

		int index = 0;
		for (int j = 0; j < 10; ++j) {
			while (!q[j].empty()) {
				arr[index++] = q[j].front();
				q[j].pop();
			}
		}
	}

}

기수정렬은 보통 가장 큰 정수의 자릿수가 작고 데이터양이 많을 때, 사용하기 때문에 알고리즘 대회에서는 배열이나 다른 컨테이너에 수를 입력받으면 메모리 초과가 발생하기 때문에 주의할 필요가 있다.