정렬8) 기수 정렬(Radix Sort)

* 기수 정렬
- 기수: 수를 나타내는 데 기초가 되는 수. 십진법에서는 0에서 9까지의 정수를 이른다. ≒기본수, 밑수, 자릿수
- 비교를 하지 않는 정렬 방법 => O(n)
    (버블, 선택, 퀵, 힙, 병합, 삽입, 셸 => 빨라도 O(nlogn) )


* 기수 정렬 로직
    1. 1의 자릿수를 보면서 각각의 버킷에 알맞게 담아준다. 버킷에서 순차적으로 뺀다면 1의 자릿수에 맞게 정렬된다.
    2. 1에 의해 정렬된 배열에서, 10의 자릿수를 비교하여 버킷에 담고 순차적으로 빼준다.
    3. 2에 의해 정렬된 배열에서, 100의 자릴수를 비교해 버킷에 담고 순차적으로 빼준다.
    4. 위 과정 반복


* 정렬 예시(queue 버킷 이용)
step0. 예시 배열


step1. 1의 자리(mod10) 를 순서대로 버킷에 넣어주기


step2. 위 1의 자리 버킷을 순서대로 배열에 돌려주기(1의 자리만 보면 오름차순 정렬 된다.)


step3. 위 정렬한 배열을 10의 자리(mod100) 를 순서대로 버킷에 넣어주기


step4. 위 10의 자리 버킷을 순서대로 배열에 돌려주기(1의 자리 정렬을 유지한채로 10의 자리 오름차순 정렬)


step5. 위 과정 반복(100의 자리)


step6. 위 과정 반복(100의 자리)


step7. 위 과정 반복(1000의 자리)


step8. 위 과정 반복(1000의 자리) => 정렬 완료



* 시간 복잡도
    1의 자리수 n번 탐색
    10의 자리수 n번 탐색
    ....
    x의 자리수 n번 탐색
    - 총 탐색 수 = x * n번
    - 최악, 최선 상관없이 항상 O(n)






참고 : 자리수를 mod 연산이 아닌 비트연산으로 더 빠르게 처리 할 수 있다.