[알고리즘] Sort - Radix sort와 정렬의 속도 비교

Sort -  Radix sort와 정렬의 속도 비교 

이어서 다음 non-comparison sort중 하나인 radix sort를 알아보자

radix sort의 조건은

1) n개의 d 자리 정수들

2) 가장 낮은 자리수부터 정렬이다.

위의 그림이 직관적으로 표현이 되어있는데

각 자릿수를 비교하며 정렬을 진행하게 된다.

여기서 중요한 것은 자릿수로 정렬을 진행할 때 다른 자리는 생각하지 않는 다는 것이다.

RADIX-SORT(A,d){
    for i<- 1 to d
        do use a stable sort to sort array A on digit i                                                     
}
 

다음은 radix sort의 슈도 코드인데 정말 간단하다.

i 번째 자릿수를 비교해서 stable 하게 연산을 진행하고,

가장 낮은 자리수 부터 가장 높은 자리수까지 d번 반복하면 되기 때문이다.

시간 복잡도는 O(d(n+k))이 된다.

여기서 n은 데이터의 개수이고 k는 데이터가 가질수 있는 서로 다른 값의 개수이다. 

지금까지 배운 알고리즘을 모두 비교해보면 다음과 같다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘