Algorithm] 기수 정렬(Radix Sort)

 

기수 정렬은 흔히 알고 있는 비교 정렬들과는 조금 다른 정렬로 볼 수 있다.

숫자를 부분적으로 비교하는 정렬이기 때문에,

제한적인 범위 내(제한적인 크기 혹은 자릿수)에 있는 숫자들에 대해서 자릿수별 정렬을 시행하는 알고리즘으로,

제한적인 상황 내에서는 어떤 비교 정렬 알고리즘에 비해서 속도가 월등하다는 장점을 가지고 있다.

단점은 직전에 말했듯, 제한적인 상황에 유효하다는 것이다.

 

089, 035, 131, 907, 910이라는 숫자가 들어왔다고 하자.

이들 입력에 대해서 각각의 자릿수(1의 자리, 10의 자리, 100의 자리)를 기준으로 정렬을 시행한다.

이 때, 작은 단위의 자릿수부터 큰 단위의 자릿수로 정렬한다.

 

내림차순 정렬을 시행한다고 하자.

 

input

089

070

131

907

910

1의 자리

089

907

131

070

910

10의 자리

089

070

131

910

907

100의 자리

910

907

131

089

070

 

눈여겨봐야 될 점이 있다.

자릿수별 정렬이 시행되는 과정에서 어떠한 경우에도 초기 자리 배치에 대한 변화가 없어야 한다는 점이다.

상대적인 위치를 뒤집어버리는 과정이 존재하면 1의 자리에서 정렬한 것이 의미가 없어짐은 물론,

중복된 숫자가 존재하는 경우 정렬의 불안정성을 초래하여

본래 앞서 있던 숫자와 그렇지 않은 숫자의 위치가 뒤바뀌는 문제가 생길 수 있다.

이러한 정렬을 불안정한 정렬이라고 하고, 상대적인 위치가 지켜지는 정렬을 안정한 정렬이라고 한다.

 

알고리즘은 아래와 같다.

 

 

input : n개의 r진수 k자리 숫자

output : 정렬 결과

for(i=1;i<=k;i++)

{

    각 숫자의 i번째 자리 수에 대한 안정한 정렬 수행.
}

return 정렬 결과(배열)

 

 

k번 반복이 진행되고, 루프 1회 당 n개의 숫자에 대한 자릿수 정보를 얻고, 이를 r개로 분류해 때문에 O(n+r)의 시간이 걸린다. 총 시간 복잡도는 O(k(n+r))로 효율이 그다지 좋아 보이지 않아 보이지만, n에 비해서 k, r이 극도로 작은 경우에는 O(n)로 볼 수 있다. 물론 그렇지 않은 경우(거의 동일한 크기와 진수가 큰 경우)에는 O(n^2)과 동일하다.

 

이렇게 작은 자릿수에서 큰 자릿수로 정렬을 진행하는 것을

LSD(Least Significant Digit) Radix Sort 혹은 RL(Right-to-Left) Radix Sort라고 하고,

이와 반대로 진행하는 것을 MSD(Most Significant Digit) 혹은 LR(Left-to-Right) Radix Sort라고 한다.

 

기수 정렬은 계좌번호, 날짜, 주민번호처럼 정해진 길이를 가지고 있으면서

양이 방대한 데이터베이스의 정렬에 사용된다.

또한, 다수 프로세서들이 사용되는 병렬 환경에서의 정렬 알고리즘에 기본 아이디어로 적용되기도 한다.