[정렬] 기수 정렬(Radix Sort)

- 원소들이 모두 d 이하의 자릿수를 가졌을 때 (d: 상수) 사용한다.

- 안정성을 유지하면서 '정렬'할 때, 0부터 9까지 표시된 10개의 공간을 준비해놓고 해당 공간에 원소를

  차례대로 넣는 방법을 사용한다.

 

안정 정렬(stable sort): 같은 값을 가진 원소들 간에 정렬 후에도 원래의 순서가 유지되도록 하는 정렬

  ex) 정렬 전 :  8  3  5  7  5’  6 정렬 후 :  3  5  5’  6  7  8

 

radix sort 작동 예

 

다음은 기수 정렬의 알고리즘이다.

radixSort(A[], d)
{
    for j ← d downto 1
        j번째 자릿수에 대해 A[1…n]을 안정성을 유지하면서 정렬;
}

 

각 digit에 대해 계수 정렬을 이용하면 O(n) 시간이 걸리고,

digit 수는 상수이므로 (예시에서 d = 4) d * O(n) = O(n)

 

따라서 최악의 경우 O(n), 평균 O(n) 시간이 소요된다.