기수 정렬 (Radix Sort )

기수 정렬 (Radix Sort )

• 정렬할 원소의 키 값을 나타내는 숫자의 자리수(radix)를 기초로 정렬하는 기법
• 사전식 정렬 방법
• 정렬하고 하는 값을 버킷에 넣어 정렬
• 버킷으로 큐 사용 (먼저 들어온 것이 먼저 출력)
• 버킷의 개수 -> 키의 표현 방법과 밀접한 관계
  • • 이진법 사용 -> 버킷 2개
    • 알파벳 문자 사용 -> 버킷 26개
    • 십진법 사용 -> 버킷 10개

기수 정렬 방법

• 첫 번째 패스 (1라운드)
  • 정렬할 키의 가장 작은 자리수를 기준으로 분배 정렬
• 두 번째 패스
  • • 두 번째 작은 자리수를 기준으로 분배 정렬
    • 키 값이 같은 경우 이전 정렬에서의 순서를 그대로 유지
• 키의 가장 큰 자리수까지 반복 수행

 

한 자리 수의 기수 정렬 수행

• 단순히 자리 수에 따라 버킷에 넣었다가 꺼내면 정렬됨

두 자리 수의 기수 정렬 예

• 일의 자리의 수 기준으로 분배 정렬
• 십의 자리의 수 기준으로 분배 정렬