CH04 : Sorting 5 - Radix Sort

 Radix Sort(기수정렬)은 입력의 제한사항으로 인해 문제의 복잡도가 $\Omega (n)$으로 내려간 경우의 정렬 알고리즘이다. (원래 정렬문제 복잡도는 $\Omega (n \log n)$) → Radix Sort는 특수한 상황에서 정렬을 $O(n)$ time에 수행하는 정렬 알고리즘이다.

Radix Sort의 Input

 기존 정렬 문제와 달리, radix sort 상황에선 다음과 같은 input에 대한 추가 정보가 주어진다.

• key값은 1부터 임의의 정수 m 사이의 정수이다.
• key값의 자릿수가 제한돼 있다. (ex. key값은 다섯자리 이하 정수)
• 각 자릿수의 값 범위가 제한적이어야 한다. (ex. 10진수 → 자릿수당 가능한 값 10개(0~9))

 즉, radix sort는 '자릿수 기반으로 정렬 가능한 정수 혹은 고정된 길이의 문자열'이라는 입력의 특수성에 기반해 동작한다. 

 그렇다면 왜 문제의 복잡도가 낮아지는가? 기본적으로 정렬 문제는 '비교 기반 정렬'이다. 내 key값과 다른 원소의 key값을 비교해 적절한 위치를 찾는 방식인 것이다. 하지만 radix sort는 비교를 하지 않고, 자릿수를 기준으로 분류하는 방식이므로 'key값끼리의 비교'라는 제한이 사라진다. (자세한 문제의 복잡도 계산은 생략!)

Radix Sort Idea

 n개의 입력을 k개의 pile로 나누고, pile을 각각 정렬 후 정렬된 파일을 합친다.

• 기존 방식 
  • n개의 element를 k개의 pile로 distribute → $O(n)$ time
  • 각 pile 정렬 → (k개의 pile) * (pile 당 원소 수 $\frac{n}{k}$) * (pile 정렬시간 $\log \frac{n}{k}$) = $ n \log \left( \frac{n}{k}\right)$
  • 정렬된 pile 합치기 → $O(n)$ time (각 바구니마다 element 하나씩 빼와서 비교)
• radix sort : 각 pile 정렬을 개선
  • merge sort 등이 아닌 자릿수 비교의 radix sort 방식을 택하여 pile 정렬을 필요없게 만듦. (어떻게 정렬하는지 구체적인 방식은 example을 참고!)

Radix Sort Example

Input & Output

• input :  다섯 자리의 양의 정수 14개. (일반화하자면, d자리의 정수 n개)
• output : 오름차순으로 정렬된 입력값들

Strategy

 d자리수임에 따라, d번의 pass를 통해 정렬하게 된다.

• first pass
  • 제일 하위 자리수를 확인 → 해당 값의 bucket에 뒤로 push
• second pass
  • 두번째 자리수를 확인 → 해당 값의 bucket에 뒤로 push
• ... 
• d번째 pass
  • d자리수를 확인 → 해당 값의 bucket에 뒤로 push

 각 bucket은 별도의 정렬을 하지 않는다. 다만, 주의할 점은 원래 원소 순서에 맞게 distribution & combine을 수행해야 한다. 

 

Radix Sort Example (다섯 자리 수 14개)

Radix Sort Structure Example. Singly Linked List의 array로 구현돼 있다.(size 10의 linked list를 갖는 array)

Radix Sort Analysis

Time complexity

하나의 원소를 distribute하는 시간

$O(1)$ time

1. i번째 자리수의 원소 값 확인 → $O(1)$ time
2. 임의의 index의 bucket 접근 → $O(1)$ time
3. linked list의 head에 삽입 → $O(1)$ time (singly linked list에서, head에서의 삽입과 삭제는 상수 시간)

 한 번의 pass에 걸리는 시간

$O(n+k)$ time

1. n개의 원소를 distribute → $O(n)$ time
2. combine : 역순으로 저장돼있기 때문에 head에서의 삭제를 통해 다시 순서를 바꿔줘야 한다. → $O(n+k)$ time
   1. i번째 bucket 접근 → $O(1)$ time * k번, $O(k)$ time k는 bucket 크기
   2. head에서의 삭제 + 다시 삽입 → $O(1)$ time * n번, $O(n)$ time
   3. i+1번째 bucket의 head와 연결 

총 소요 시간

$O(d(n+k))$ time

1. 모든 pass 고려 → $O(n+k)$ time * d번, $O(d(n+k))$ time d는 최대 자리수

 d, k는 constant이면, 결론적으로 $O(n)$ time이 걸린다. → d, k가 constant가 아니면 time complexity가 늘어남에 유의! 둘이 상수인지를 꼭 고려해줘야 한다. 

Space Complexity

 입력으로 주어지는 n개의 원소를 저장하기 위해 $O(n)$ space + 추가적으로 $\Theta (n)$ space

• 정확히는, 
  1. bucket을 위해 size k인 array
  2. linked list에 total n개가 저장
  3. 따라서 $\Theta (n+k)$ space

 그렇기에 점근적으로 $O(n)$ space가 필요하지만, time complexity때처럼 k가 상수인지를 꼭 고려해줘야 한다. 

Stable Algorithm인 Radix Sort

Stable Algorithm

 위와 같이 중복된 x가 몰려서 저장되는 상황에서, x의 상대적인 순서가 유지되면 stable한 알고리즘이라고 한다.

Stable Algorithm인 Radix Sort

 Radix Sort에서는 원래 원소 순서에 맞게 distribution & combine이 되기 때문에 stable한 알고리즘이 된다. stable함이 중요하기 때문에 특정 STL에서는 stable_sort()라는 함수가 있기도 하다. 다른 정렬 알고리즘도 적절히 처리해 주면 stable 알고리즘이 될 수 있다. 

Radix Sort Algorithm 

List radixSort(List L, int radix, int numFields)

List[] buckets = new List[radix];
int field; //field number within the key
List newL;
newL = L;
for (field = 0; field<numFields; field++)
    initialize buckets array to empty list
    distribute (newL, buckets, radix, field);
    newL = combine(buckets, radix);
return newL;

void distribute(List L, List[] buckets, int radix, int field)
//distribute keys into buckets

List remL;
remL = L;
while(remL!=nil)
    Element K = first(remL);
    int b = maskShift(field, radix, K.key);
        //maskShift(f, r, key) selects field f(counting from the right) of key,
        //based on radix r. the result, b, is tthe range 0...radix-1,
        //and is the bucket number for K
    buckets[b]= cons(K, buckets[b]); //construct list
    remL=rest(remL);
return

List combine(List[] buckets, int radix)
//combine linked lists in all buckets into one list L

int b; //bucket number
List L, remBucket;
L= nil;
for (b=radix-1; b>=0; b--)
    remBucket = buckets[b];
    while(remBucket != nil)
        key K= first(remBucket);
        L= cons(K,L);
        remBucket = rest(remBucket);
return L;