04. 기수 정렬

기수 정렬의 정의

• Radix Sort는 자릿수를 기준으로 차례대로 데이터를 정렬
• 각 자릿수를 기준으로 분류하여 가장 큰 자릿수가 D일 때
  --> O(DN)의 시간 복잡도

기수 정렬의 과정

기수 정렬의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 10000

void radixSort(int* a, int n) {
	int res[MAX]; //결과 배열
	int maxValue = 0;
	int exp = 1; // 자리수

	for (int i = 0; i < n; i++) {
		if (a[i] > maxValue)  maxValue = a[i]; 
	}
	// 1의 자리부터 계산
	while (maxValue / exp > 0) { // 최대값의 자리수만큼 while문 반복
		int bucket[10] = { 0 };
		// 자릿수 배열 처리
		for (int i = 0;i < n;i++) bucket[a[i] / exp % 10]++;
		// 누적 계산
		for (int i = 0; i < 10; i++) bucket[i] += bucket[i - 1];
		//같은 자리수끼리는 순서 유지
		for (int i = 0;i >= 0;i--) res[--bucket[a[i] / exp % 10]] = a[i];
		// 기본 배열 갱신
		for (int i = 0;i < n;i++) a[i] = res[i];
		exp *= 10; // 다음 자리수 진행
	}
}

int main(void) {
	int a[MAX];
	int i, n;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	radixSort(a, n);
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	system("pause");
	return 0;
}

계수정렬보다 약간 느리지만 숫자가 매우 큰 상황에서도 사용 가능