자료구조: 기수 정렬(Radix Sort)

기수정렬이란?

낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘

비교 연산을 하지 않아 정렬 속도가 빠르지만  데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요한다.

 

각 데이터의 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간복잡도를 갖는다.

 

LSD(Least Significant Digit) vs MSD(Most Significant Digit)

LSD 기수 정렬은 가장 작은 자릿수부터 정렬을 진행해 나가는 방식이다.

마지막까지 결과를 알수 없는 것이 단점이지만 프로그래밍에서는 장점이 된다.

 

MSD 기수 정렬은 가장 큰 자릿수부터 정렬을 진행해 나가는 방식이다.

끝까지 가지 않아도 중간에 정렬이 완료될 수 있다는 점이 장점이다.

중간에 데이터를 점검해야 하기 때문에 구현이 복잡해질 수 있다.

 

코드

// 기수 정렬(Radix sort)
// 자릿수를 기준으로 데이터를 정렬하는 알고리즘
// 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 필요
// 시간복잡도 : 가장 큰 자리수를 D라고 했을때 D*N의 시간복잡도를 갖는다.

#define _CRT_SECURE_NO_WARNINGS
#include 
#define MAX 10000

void radixSort(int *a, int n) {
	int result[MAX], maxValue = 0;
	int exp = 1;
	for (int i = 0; i < n; i++) {
		if (a[i] > maxValue) maxValue = a[i];
	}
	while (maxValue / exp > 0) { // 1의 자릿수 계산
		int bucket[10] = { 0 };
		for (int i = 0; i < n; i++) bucket[a[i] / exp % 10]++; // 자릿수 배열 처리
		for (int i = 1; i < 10; i++)bucket[i] += bucket[i - 1]; // 누적 계산 : 결과 배열을 만들기 위해서!	
		for(int i=n-1; i>=0;i--){ //같은 자릿수 끼리는 순서를 유지
			result[--bucket[a[i] / exp % 10]] = a[i];
		}
		for (int i = 0; i < n; i++) a[i] = result[i]; // 기본 배열 갱신
		exp *= 10;
	}
}

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

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