기수 정렬(Radix sort)

▶기수 정렬 (Radix sort)

---

자리 수가 존재하는 데이터들의 경우 적용 가능한 방법이다. (안정 정렬이 보장됨)

e.g) OO자리 양의 정수, 문자열

가장 큰 자리수 혹은 작은 자리 수부터 선입 선출 방식의 자료구조에 분류해서 저장한 뒤, 해당 자리의 숫자가 작은 것부터 데이터를 꺼내 정렬하는 과정을 더 이상 크거나 작은 자리 수가 존재하지 않을 때까지 반복하여 정렬을 완료한다. 정렬에 O(dN)의 시간이 걸리며, d는 정렬해야 할 데이터의 최대 자리 수를 말한다. 빠른 속도로 정렬이 가능하나, 데이터를 분류해서 저장하는 데 필요한 공간이 더 필요하다는 단점이 있다. 같은 데이터 값이더라도 그 순서가 뒤바뀌지 않는 안정 정렬이다.