[Algorithm] 기수 정렬 (Radix Sort)

기수정렬?

• 데이터끼리의 직접적인 비교 정렬이 아닌, 숫자를 부분적으로 비교하는 정렬방법
• 제한적인 범위 내에 있는 숫자에 대해서 낮은 자릿수부터 자릿수 별로 비교 정렬하는 알고리즘
• 어느 비교 정렬 알고리즘보다 빠른 큰 장점!!

 

기 (Radix)?

• 특정진수를 나타내는 숫자들
• 10진수의 기 : 0,1,2,3,4,5,6,7,8,9
• 2진수의 기: 0,1

 

 

🚫주의할 점

• 10의 자리가 같을 때 왜 035가 131 위에 위치하면 안되는 것인가? -> 1의 자리에 대해 정렬해 놓은 것이 아무 소용이 없게 되기 때문이다.

❗️정렬알고리즘은 안정성을 가진다.

• 입력에 중복된 숫자가 있을 때, 정렬된 후에도 중복된 숫자의 순서가 입력에서의 순서와 동일하다.

 

 

💡RadixSort 알고리즘 (의사코드)

• 입력 : n개의 r진수의 k자리 숫자
• 출력 : 정렬된 숫자

• for i=1 to k  // 1의 자리~k자리까지 반복 수행
  각 숫자의 i자리 숫자에 대해 안정한 정렬을 수행한다. (이전 정렬의 순서 유지)
  return 배열A

• 입력 숫자가 r진수라면, i자리가
  1. '0' 인 수의 개수
  2. '1' 인 수의 개수
  3. ...
  4. '(r-1)'인 수의 개수를 각각 계산하여 i자리가 '0'인 숫자로부터 '(r-1)'인 숫자까지 차례로 안정성에 기반을 두어 정렬한다.

 

 

⏰시간복잡도

• 먼저 for-loop가 k번 반복된다. ( k는 입력 숫자의 최대 자릿수 )
  • loop 한번에, n개의 숫자의 i번째 자리 수를 읽으며, 각 자리수에서는 r개로 분류하여 각각 개수를 세고, 그 결과에 따라 숫자가 이동하므로 O(n+r)시간이 걸린다.
• 따라서 시간 복잡도는 O(k(n+r))
• 여기서 k 나 r이 입력 크기인 n보다 크지 않으면, 시간 복잡도는 O(n)이 된다.
  • 예를 들어, 4byte ( 32 bit ) 숫자를 정렬할 때, n=2^32라고 가정하고, r=2^4 즉 16진수라고 정하면, 입력 숫자는 k=8 즉 8자리의 16진수가 된다.
  • 이때의 시간 복잡도는 O(k(n+r)) = O(8(2^32+16))
  • 그런데, 8이나 16은 2^32과 비교하면 매우 작은 수 이므로, 이때의 시간 복잡도는 O(2^32) = O(n)

 

❗️장점

• 정수와 같은 자료의 정렬 속도가 매우 빠르다.

❗️단점

• 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

 

Least Significant Digit (LSD) 기수 정렬 & RL (Right-to-Left) 기수 정렬 : RadixSort가 1의 자리부터 k자리로 진행

Most Significant Digit (MSD) 기수 정렬 & LR (Left-to-Right) 기수 정렬 : RadixSort가 k자리부터 1의 자리로 진행

 

---

Reference

• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업
• 알기쉬운 알고리즘 도서