정렬: radix sort

counting sort는 전체 원소의 최대값 만큼 counting table을 할당 해서 처리해야 하므로

원소 값들의 차이가 클 때는 불리한 면이 보입니다.

그래서 counting sort 같이 각 원소들의 우선 순위를 비교하지 않는 방법이면서

어떤 묶음 단위로 계층적으로 처리하면 이에 대한 단점을 보완할 수 있기 때문에 radix sort를 사용합니다.

radix는 base라고도 하며 2진법, 10진법, 16진법 같은 개념입니다.

그런데 꼭 radix sort는 기존 몇 진법에 따라서만 사용하는 것이 아니라

필요에 따라 1000진법 같은 효율적은 묶음 단위 방법으로 사용해도 좋을 것 같습니다.

10진수로 고정하여 C/C++로 아래와 같이 구현해 보았습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

static int power_of_order(int order_10)
{
	int result = 1;
	for (int i = 0; i < order_10; i++) {
		result *= 10;
	}
	return result;
}

void counting_sort(int *data, int len, int order_10)
{
	int counting_table[10] = { 0, }; // 10진법 bucket은 10개로 고정 후 0로 초기화
	int *indices = new int[len]; // counting_table index를 다시 계산하지 않기 위해 저장
	int *sorted_data = new int[len];
	int p = power_of_order(order_10); // 지정된 자리수를 최소 자리수로 맞추기 위한 나눔수 계산

	for (int i = 0; i < len; i++) { // 해당 원소 bucket의 count 증가
		indices[i] = (data[i] / p ) % 10; // 해당 원소에서 지정된 자리수가 최소가 되도록 조정하고 그 값을 구함
		counting_table[indices[i]]++; // 지정된 자리수에서 해당 원소의 bucket count 증가
	}

	for (int i = 1; i < 10; i++) { // 각 bucket의 counting 누적값 계산
		counting_table[i] += counting_table[i - 1];
	}

	for (int i = (len-1); i >= 0; i--) { // 해당 원소의 counting 누적값을 거꾸로 빼면서
		int index = counting_table[indices[i]] - 1; // 누적 counting 값을 정렬된 배열의
		sorted_data[index] = data[i]; // index로 사용
		counting_table[indices[i]]--; // 동일 bucket의 다음 원소는 앞으로 배치하기 위해
	}

	for (int i = 0; i < len; i++) {
		data[i] = sorted_data[i]; // 다음 order의 정렬을 수행하기 위해 다시 원본 data에 복사
	}

	delete[] indices;
	delete[] sorted_data;
}

void radix_sort(int *data, int len)
{
	// radix 10진법으로 3자리까지 정렬
	for (int order_10 = 0; order_10 < 3; order_10++) {
		counting_sort(data, len, order_10);
	}
	printf("Data Size %d\n", len);
	for (int i = 0; i < len; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
}