기수 정렬(radix sort)

👉 기수 정렬이란?

• 정수를 정렬하는 비교하지 않는 정렬 알고리즘
• 각 숫자를 자릿수(digit)별로 비교하여 정렬하는 방식으로 작동
  • 예를 들어, 10진수의 경우 1의 자리, 10의 자리, 100의 자리 등을 차례로 비교
    
    
    
    

👉 기본 과정

• 가장 낮은 자릿수부터 정렬 시작
  • 기수 정렬은 일반적으로 가장 낮은 자릿수(예: 1의 자리)부터 시작해서, 가장 높은 자릿수까지 진행
• 각 자릿수마다 버킷에 분배
  • 각 자릿수의 숫자(0~9)에 따라 10개의 버킷(bucket)으로 숫자들을 분배
  • 예를 들어, 1의 자리가 5인 모든 숫자는 같은 버킷에 들어가게 됨
• 버킷에서 숫자를 꺼내어 재배열
  • 0번 버킷부터 9번 버킷까지 차례로 숫자를 꺼내어 다시 배열
• 다음 자릿수로 이동
  • 다음 높은 자릿수로 넘어가서 2번과 3번 과정을 반복
    • 기존에 정렬된 순서를 바탕으로 다시 정렬하기 때문에 점차 정렬된 상태로 변하게 됨
• 모든 자릿수를 정렬하면 완료
  • 가장 높은 자릿수까지 정렬을 마친 후, 배열은 완전히 정렬된 상태가 됨
    
    
    
    

👉 예시

• 배열 [170, 45, 75, 90, 802, 24, 2, 66]을 기수 정렬로 정렬
  1. 1의 자리 정렬
     • 170, 90은 0번 버킷
     • 1번 버킷은 비어 있음
     • 802, 2은 2번 버킷
     • 3번 버킷은 비어 있음
     • 24, 4번 버킷
     • 45, 75, 5번 버킷
     • 66, 6번 버킷
     • ...
     • 정렬 결과 : [170, 90, 802, 2, 24, 45, 75, 66]
  2. 10의 자리 정렬
     • 2, 24은 0번 버킷
     • 1번 버킷은 비어있음
     • 45은 4번 버킷
     • 66은 6번 버킷
     • 75, 7번 버킷
     • 80, 8번 버킷
     • 90, 9번 버킷
     • 170은 7번 버킷 (170의 10의 자리는 7)
     • 정렬 결과 : [2, 24, 45, 66, 75, 170, 802, 90]
  3. 100의 자리 정렬
     • 같은 방식으로 100의 자리를 정렬하면, 최종적으로 [2, 24, 45, 66, 75, 90, 170, 802]가 됨