Radix Sort (기수 정렬)

| O(n) 정렬

비교 정렬의 하한은 O(nlogn)이지만 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 O(n) 정렬이 가능하다. 대표적인 O(n) 정렬의 알고리즘으로는 Counting Sort와 Radix Sort가 있다.

---

| Radix Sort

Radix Sort 또한 자료의 원소가 제한적인 성질을 만족하는 경우 사용 가능한 O(n) 정렬 방법이다. 원소의 자릿수가 d자리 이하인 N개의 수들로 이루어진 경우 O(d * N)의 시간 복잡도를 갖는 정렬방법이다. 소개할 Radix Sort 구현 방법은 Counting Sort를 활용하는 방법이다. 낮은 자리부터 정렬을 하고 정렬된 순서를 유지하면서 보다 높은 자리를 정렬하는 과정에서 Counting Sort가 활용된다. 따라서 개수를 셀(Counting 할) 배열과 결과가 저장될 배열이 추가로 필요하다.

우리가 일반적으로 사용하는 10진수 기반의 Radix Sort의 기본 구현 방법은 아래와 같다.

const int SIZE = 10;
const int DIGIT = 4;
int N, arr[SIZE], temp_arr[SIZE], cnt[10];

void radixSort(){
	int i, j, decimal = 1;
    for(i = 0; i<DIGIT; decimal *= 10) {
        // 계수정렬 코드 start 
        for(j = 0; j<10; j++) cnt[j] = 0; // 배열 초기화
        for(j = 0; j<N; j++) cnt[arr[j] / decimal % 10]++; // 카운팅
        for(j = 1; j<=10; j++) cnt[j] += cnt[j-1]; // 누적합
        for(j = N-1; j>=0; j--) {
            temp_arr[--cnt[arr[j] / decimal % 10]] = arr[j];
        }
        // 계수정렬 코드 end 
        for(j = 0; j<N; j++) arr[j] = temp_arr[j];
    }
}

코드를 살펴보면 8~13번 line까지는 counting 정렬에 활용되는 방법이다. 이 방법을 사용한다면, 만약 자릿수의 숫자가 같은 경우에도 정렬 후 기존 위치를 유지할 수 있다는 장점이있다. 즉, 이런 방식의 Radix Sort는 안정 정렬의 일종이라 볼 수 있다.

| Radix Sort 심화

위의 코드의 시간 복잡도는 O(자릿수 * 자료 개수)로 데이터의 개수가 많지 않은 경우 잘 수행된다. 하지만 자릿수가 늘어나고, 데이터의 크기가 커진다면 시간이 많이 걸린다. 그 이유는 자릿 수 별 계수 정렬을 위한 나눗셈과 나머지 연산을 하는 부분에 있다.

| cnt[arr[j] / decimal % 10]에 대한 고찰

1. 코드는 나눈 몫을 나머지 연산하는 것인데, 나눗셈 연산이 다른 사칙연산에 비해 시간이 오래 걸린다.
2. 나머지 연산은 나눗셈 연산보다 더 오래 걸린다. 왜냐하면 내부적으로 a % b 는 a - a / b * b로 계산되기 때문이다.
3. 즉, 위의 두 연산의 속도가 Radix Sort의 성능을 저하시킨다. 이를 해결하기 위한 방법으로는 비트 연산자를 생각할 수 있다.

a / b 형식에서 b가 2의 제곱수인 경우 시프트 연산자(>>) 를 활용할 수 있고, 나머지 연산은 '&' 를 활용할 수 있다. 이 부분은 아래 예를 통해 쉽게 이해 가능하다.
127 / 8 => 127 >> 3 => 0111 1111(이진수) >> 3 => 0000 1111 = 1111(15)
127 % 8 => 127 & 7 => 0111 1111 & (1000 - 1) => 0111 1111 & 0000 0111 = 0111(7)

따라서 10진 기수가 아닌 2의 제곱수인 8진수, 16진수, 256진수, 65536진 기수 등 2의 제곱수 진법을 생각할 수 있다.
다만 여기서는 실험적으로 가장 효율이 좋은 256진법으로 위 문제를 다시 해결해보자.

const int SIZE = 10;
const int BASE = (1<<8); // 256 진수 사용을 위한 BASE
const int MASK = (BASE - 1); // % 연산을 위한 MASK
// const int DIGIT = 4; // 10진수 Radix Sort에 사용된 부분은 삭제 
int N, arr[SIZE], temp_arr[SIZE], cnt[BASE];

먼저 다른 부분은 동일하지만, 256진법 사용을 위해 BASE와 MASK를 정의해주었고, 이를 위한 cnt 배열의 개수도 BASE만큼 할당해준다.

const int SIZE = 10;
const int BASE = (1<<8); // 256 진수 사용을 위한 BASE
const int MASK = (BASE - 1); // % 연산을 위한 MASK
int N, arr[SIZE], temp_arr[SIZE], cnt[BASE];

void radixSort() {
	for(i = 0; i<32; i += 8) {
		int i, j;
   		int *ap = arr, *bp = temp_arr, *tp // 포인터를 이용한 swap을 위한 할당. 
    
		// 계수정렬 코드 start 
	    for(j = 0; j<BASE; j++) cnt[j] = 0; 
	    for(j = 0; j<N; j++) cnt[(ap[j] >> i) & MASK]++; // 나눗셈, 나머지 연산이 비트연산으로 바뀌었다.
	    for(j = 1; j<=BASE; j++) cnt[j] += cnt[j-1]; 
	    for(j = N-1; j>=0; j--) {
    		bp[--cnt[(arr[j] >> i) & MASK]] = ap[j];
    	}
    	// 계수정렬 코드 end 
    
    	tp = ap, ap = bp, bp = tp; // 다음 radix 정렬을 위한 swap. 
    }
}

256진법 자체에 거부감이 드는 것이 당연하다. 보통 2진법 혹은 16진법 정도만 접해봤지, 256진법은 표현 자체도 어려운 게 사실이다. 쉽게 생각해보면 우리가 익숙한 10진법이 0부터 9까지를 한 자릿수로 표현하는 것처럼, 256진법은 0부터 255까지를 (표현할 순 없지만) 한 자릿수로 여기는 것뿐이다.