기수 정렬 (Radix Sort (LSD))

(출처: Introduction to Algorithms)

 

 

기수 정렬 알고리즘

선형 시간 정렬 중 하나인 기수 정렬(Radix Sort, 레이딕스 소트) 알고리즘을 알아봅시다.

천공카드(punched card) 쓰던 시절 천공카드를 정렬할 때 사용하던 방법이 기수 정렬이라고 합니다.

 

Fig 1. Example of Radix Sort (LSD)

기수 정렬은 자릿수 단위로 정렬을 하는 정렬 방법입니다. 두 가지 방법이 있습니다

• MSD(Most Significant Digit)
  • 가장 큰 자리수부터 시작해 가장 작은 자리수까지 정렬합니다.
• LSD(Least Significant Digit)
  • 가장 작은 자리수부터 가장 큰 자리수까지 정렬합니다

둘 다 선형 시간 정렬인 점은 동일한데, 약간의 차이가 있습니다.

이 글에서는 LSD Radix Sort를 기준으로 설명하겠습니다.

 

낮은 자릿수에서 높은 자릿수까지 정렬을 하면 모든 수가 정렬됩니다. 이때 중요한 점은 각 자릿수마다 정렬할 때 안정된 정렬(stable sort)을 사용해야 한다는 점입니다.

 

Fig 2. pseudo-code of Radix Sort (LSD)

알고리즘은 간단합니다.

각 자릿수마다 정렬할 때는 보통 계수 정렬(Counting sort)을 사용합니다.

 

결과적으로 d자리 숫자가 n개 주어지고, 각 자리에 값이 k개 들어갈 수 있을 때, \(\Theta(n+k)\) 시간이 걸리는 안정된 정렬을 사용하면, 기수 정렬은 이 숫자들을 \(\Theta(d(n+k))\) 시간에 정렬할 수 있습니다.

 

 

장점과 단점 (Pros and Cons)

LSD Radix Sort 기준입니다.

•  장점
  • 선형 시간에 수행된다: \(\Theta(d(n+k))\)
  • 안정된 정렬(stable sort)이다
• 단점
  • 각 자릿수마다 정렬할 때 계수 정렬을 보통 사용하는데, 내부 정렬이 아니다 = 메모리를 추가로 사용한다

 

 

퀵소트보다 좋을까?

기수 정렬이 \(\Theta(n\lg n)\)의 평균 수행시간을 갖는 퀵소트보다 항상 나을까요? 꼭 그렇지는 않다고 합니다.

• 내부 정렬이 아님
• 퀵 정렬이 보통 기수 정렬에 비해 캐시를 효율적으로 사용함
• big-O notation에 숨은 상수 인자가 다르다

사용 기계, 입력 자료 등의 특성에 따라 달라질 수 있다고 하니 '선형 시간 정렬 알고리즘이 항상 nlgn 알고리즘보다 좋다'는건 아니라고 알아두면 될 듯 합니다.