Radix Sort

- Radix sort는 데이터의 크기가 커서 Counting Sort가 불가능한 경우 몇 번에 나누어서 처리하는 방법

- data = {254, 535, 892, 250, 862, 891, 155, 367, 445}

- 물론 counting sort도 가능한 범위이지만, radix sort는 한자리씩 나누어서 3번에 정렬하는 방법을 사용해 봄

1. 1의 자리를 기준으로 정렬을 함

2. 10의 자리를 기준으로 정렬을 함. 10의 자리가 같은 경우에 기존의 순서를 유지함

3. 100의 자리를 기준으로 정렬을 하되 같은 경우에 기존의 순서를 유지하면 최종 정렬이 완성됨

 

결국 radix sort는 counting sort를 몇 번 나누어서 실행하는 것임

키 값의 크기를 정하는 방법에 따라 성능의 차이가 있는데, 일반적으로 8bit로 하는 경우 우수한 성능

데이터를 a[i]를 네 번으로 나누는 방법

(a[i] >> 0)%P, (a[i] >> 8)%P, (a[i] >> 16)%P, (a[i] >> 24)%P

참고로 mod 연산인 (a[i] >> 0) % p 는 (a[i] >> 0) & (p-1)과 같음

 

#include <stdio.h>

#define KEY (a[i] >> k) & mod // KEY 라는 것은 정렬에 사용하는 8bit를 의미함
int A[101], B[101]; //데이터의 숫자임
int N = 9;
const int P = (1 << 8); // 8bit만 사용하겠다. 성능 우수함
const int mod = P - 1; // mod 연산을 빠르게 하기 위해서 원래 나누려는 값에서 1을 빼고, & 연산을 수행함

// 이렇게 했을 때 4 * (2P + 2N) 시간 복잡도
void radixsort(int* a, int* b) {
	int i, k, *t, cnt[P + 1];
	for (k = 0; k < 32; k += 8) { // 32bit를 8bit씩 나눠서 4번 돌림
		for (i = 0; i <= P; i++) cnt[i] = 0;  // 초기화
		for (i = 0; i < N; i++) cnt[KEY]++; // 아 하나의 숫자를 4번에 나눠서 cnt 배열에 숫자를 카운팅 함
		for (i = 1; i <= P; i++) cnt[i] += cnt[i - 1]; // 누적합을 저장함
		for (i = N - 1; i >= 0; i--) b[--cnt[KEY]] = a[i]; // 기존 순서 유지를 위해서 뒤쪽부터 채움
		t = a; a = b; b = t; // tmp 배열을 이용하여 다시 a값을 돌림 
	}
}

int main()
{
	int a[] = { 254, 535, 892, 250, 862, 891, 155, 367, 445};
	int b[9] = { 0 };
	radixsort(a, b);
	for(int i = 0; i < N; i++) 
		printf("%d ", a[i]);

	return 0;
}

 

- 실제 복잡도는 4 * (2P + 2N)임

- 기존 순서를 유지하기 위해서 뒤쪽부터 채움