[Algorithms] Radix Sort | 기수 정렬

Radix Sort

기수 정렬

- 입력값들을 자릿수별로 정렬시켜 나가는 알고리즘이다.
- 입력이 모두 \(k\) 자릿수 이하의 자연수인 특수한 경우에 사용할 수 있다.
- Time Complexity = \(\Theta(n)\)
- 입력에 제한이 있는 특수 정렬 알고리즘으로, 제한이 있는 대신 비교 정렬 알고리즘보다 좋은 성능의 수행 시간을 보인다.

---

Mechanism (메커니즘)

- 입력값들의 아랫 자릿 수 부터 정렬해나아간다.
- Stable Sort* 특성을 보인다.
- 각 자릿수별로 정렬 시에, 기존의 비교 정렬 알고리즘을 사용하지 않고, 0~9까지 표시된 공간을 마련해서 해당 자릿수와 일치하는 원소를 저장하는 방식으로 구현한다.
(이 원리가 지켜져야 기수 정렬이 입력값에 제한을 두는 대신 다른 비교 정렬 알고리즘들 보다 빠르게 동작할 수 있게 된다.)

* Stable Sort(안정성을 유지한 정렬) : 한 번 정렬된 원소들 중, 값이 같은 원소끼리는 남은 정렬과정이 진행되어도 순서가 바뀌지 않는 것을 의미한다.

---

Pseudo Code (의사 코드)

radixSort(A[], n, k) {
// k자릿수의 입력값들은 저장한 A[1...n]을 기수 정렬한다.

    for i ← 1 to k{
        i번째 자릿수에 대해 A[1...n]을 Stable Sort한다.
        // 반드시 안정성을 유지하며 O(n) 시간 내에 정렬해야 함을 명심하자
    }
}

---

Performance Evaluation (알고리즘 성능 평가)

- 입력 조건이 지켜진다는 가정 하에, \(\texttt{radixSort}\)에 소요되는 시간은 \(O(n)\) 이다.

pf) \(k\)번 반복되는 \(\texttt{for}\) Loop에서 \(k\)는 상수이므로 실행 시간에 영향을 주지 않는다.