기수정렬(Least Significant Digit 방식) 관련 글들을 찾아보면 개념을 쉽게 설명하기 위해 십진수 단위를(base 10) 사용한 것들이 많은데 실제로 이것을 구현하면 생각보다 느린 것을 볼 수 있다. 나눗셈 연산과 나머지연산이 수행되기 때문이다.  예를 들어 100의 자리에서 기수정렬할 단계를 보면, (현 상태에서 m은 100이라고 가정한다.)


arr[i]/m%10    


위와 같이 / 연산과 % 연산이 사용된다.



 이러한 문제를 개선하기 위해 버킷의 개수를 2의 거듭제곱으로 하면 속도가 빠른 비트연산을 사용할 수 있다. 버킷의 개수를 8로 하면 위 연산식이 아래와 같이 된다. (현 상태에서 m은 64라고 가정)


(arr[i]>>m)&7


2의 거듭제곱으로 나누었을 때의 나머지는, 굳이 나누어서 계산해볼 필요 없이 해당 위치의 비트만 AND연산으로 추출하면 되는 것이다.




구현


 아래 코드는 0부터 99,999,999까지의 정수 데이터들을 정렬할 수 있는 기수정렬(base 8) 알고리즘을 코드로 구현한 것이다. 

     for(int i=0; i<9; ++i) {


           idx = 0;

       for(int j=0; j<8; ++j) {
            counts[j] = 0;
        }
     
        for(int j=0; j<n; ++j) {
            digit = (arr[j]>>i*3)&7;
            bucket[digit][counts[digit]++] = arr[j];
        }
    
        for(int j=0; j<8; ++j) {
            for(int k=0; k<counts[j]; ++k) {
                arr[idx++] = bucket[j][k];
            }
        }
    }


비트시프트 연산을 보면, i는 데이터를 8진수로 나타냈을 때 특정 자리의 숫자를 얻을 때 사용된다. i를 8이 될때까지만 반복시키는 이유는  으로, 99,999,999를 8진수로 나타낼 수 있는 가장 큰 자릿수가 8이기 때문이다.




수행시간 분석


 base 8 기수정렬에서 전체 데이터의 양을 N개라고 했을 때 버킷의 크기는 bucket[8][N]이다. base 8 대신 base 4나 base 2를 사용하면 메모리 사용량은 각각 2배, 4배 줄어들게 된다. 반면, 기수정렬의 시간복잡도가 O(dN)이므로, 수행시간은 더 늘어난다. (d는 해당 base에서 데이터의 최대 자릿수이다.) 표 1은 내림차순으로 정렬된 100만개 ~ 500만개 데이터를 오름차순으로 정렬했을 때 각 알고리즘의 수행 시간(ms)이다. 표 2는 랜덤함수로 생성한 무작위 데이터를 오름차순으로 정렬했을때의 결과이다.


표 1


표 2




 표 1의 결과를 그래프로 나타내 보면 다음과 같다.




 base 8 대신 16이나 32를 사용하면 메모리 사용량이 늘어나고, 속도가 약간 줄어들겠지만, 값 복사시간이 기본적으로 존재하기 때문에 속도가 줄어드는 데에는 한계가 있다. 수행시간이 카운팅 정렬을 사용했을때 이하로 떨어지지는 않을 것이다.


+ Recent posts

티스토리툴바