Radix Sort

Radix sort

• 키값에 대한 속성이 주어졌을 때, 비교 연산이 아닌 다른 연산을 사용해 linear time에 정렬을 수행할 수 있다.
• 속성 예시
  : 이름, 다섯 자리 10진수, 범위가 정해진 정수
• 정렬 과정
  1. 서로 다른 pile에 분배 - θ(n)
  2. 각각의 pile을 정렬
  3. 정렬된 pile들을 합침 - θ(n)
• 최하위 숫자(or 비트, 문자, 필드)순으로 pile에 분배하면 정렬 과정을 생략 가능
• Total O(d*(n+k))  (d: 필드 수(ex. 다섯 자리 십진수에서 5), k: pile 수(ex. 다섯 자리 십진수에서 10(0~9)))
  -> d, k가 constant라면 θ(n)