기수정렬

• 숫자를 부분적으로 비교하며 정렬하는 알고리즘
• 기(radix)는 특정 진수를 나타내는 숫자들을 의미
  • 10진수의 기: 0, 1, 2, ..., 9
  • 2진수의 기: 0, 1
• 기수 정렬은 제한적인 범위 내에 있는 숫자에 대해 각 자릿수별로 정렬을 수행하는 알고리즘
  

1. LSD 기수 정렬

• RadixSort는 1의 자리부터 k자리로 진행하는 경우, Least Significant Digit(LSD) 기수 정렬 또는 RL(Right-to-Left)기수 정렬이라고 부름
  

2. MSD 기수 정렬

• k자리부터 1의 자리로 진행하는 방식은 Most Significant Digit(MSD) 정렬 또는 LR(Left-to-Right)기수 정렬이라 부름
  
• 이전 자리의 정렬이 된 것을 고려하여 정렬

3. 시간복잡도

• for-루프를 입력의 최대 자릿수만큼 반복
• 루프가 1회 수행할 때 마다 n개의 숫자의 i번째 자리수를 읽으며, r개로 분류하여 세고, 그결과에 따라 숫자가 이동하니 O(n+r)
• 결과적으로 O(k(n+r))이니 O(n)