[Sort]Radix sort(기수 정렬)

설명

• 자리수를 비교해서 정렬하는 방식
• 자리수가 없는 자료형에 대해서는 정렬이 불가능 합니다.
• 추가적인 메모리가 필요합니다.
• Conunting Sort와 마찬가지로 비교를 수행하지 않는 알고리즘 입니다.

예제

MSD (Most Significant Digit) : 가장 큰 자릿 수를 의미

LSD (Least Significant Digit : 가장 작은 자릿 수를 의미 

방법 1 MSD → LSD

이 방법은 정렬을 수행하기 위해 그룹을 만들어야 한다는 단점이 있습니다.

만약 그룹을 만들지 않고 2번째 자리수를 비교하게 된다면 앞에서 정렬한 자료들의 순서가 엉망이 될 것입니다.

이러한 단점을 극복하고자 다음 방법이 주로 사용됩니다.

 

방법 2 LSD → MSD

이 방법은 따로 그룹을 만들지 않더라도 정렬이 가능합니다.

그리고 Stable Sort(안정 정렬)이 가능하게 됩니다.

 

Pusedo Code

RADIX_SROT(A, d)
	for i = 1 to d
    	use a stable sort to sort array A on digit i
        # i번째 자리에 대해서 Stable Sort를 수행

stable sort : counting sort 와 같은 방법을 이용할 수 있습니다.

 

시간 복잡도

• \(O(d(n+k)\)
  d : 자리 수
  n : 데이터 갯수
  k : 각 자리에 들어갈 수 있는 가능한 가지 수
  ex) 10진수 → 10개, 16진수 → 16개
• 일반적으로 d는 상수이고 \(k = O(n)\) 이므로 \(O(N)\)의 시간 복잡도를 가지게 됩니다.

 

이 때 d와 k를 변경해서 정렬이 가능합니다.

왼쪽 그림 같은 경우는 일반적인 경우로 d = 4 k = 10인 경우입니다.

이를 오른쪽 그림 같이 d = 2 k = 100 으로 변경한다면 자리수가 큰 데이터에 대해서 더 빠르게 동작할 수 있게 됩니다.