radixsort.cpp

#include <vector>
#include <climits>
#include <cstdlib>
#include <iostream>

using namespace std;

#define max(a, b) a > b ? a : b

void radixsort(vector<int>& arr, int n) {
	vector<int> tmp(n);
	int maxv = INT_MIN;
	for (int i = 0; i < n; i++) {
		maxv = max(maxv, arr[i]);
	}

	int exp = 1;
  	/* 가장 큰 수의 자릿수만큼 */
	while (maxv / exp > 0) {
		int res[10] = { 0 };
    		/* 해당 자릿수 정보 수집 */
		for (int i = 0; i < n; i++) {
			res[arr[i] / exp % 10] += 1;
		}
    		/* 위치 정보를 알기 위해 자릿수 정보 누적 */
		for (int i = 1; i < 10; i++) {
			res[i] += res[i - 1];
		}
    		/* 실제 자리에 대입 */
		for (int i = n - 1; i >= 0; i--) {
			int x = arr[i] / exp % 10;
			tmp[--res[x]] = arr[i];
		}
		for (int i = 0; i < n; i++) {
			arr[i] = tmp[i];
		}		

		exp *= 10;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	radixsort(arr, arr.size());
	for (int i = 0; i < n; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}