기수 정렬(Radix Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

기수 정렬(Radix Sort)

• 정렬할 원소의 키 값을 나타내는 숫자의 자리수(radix)를 기초로 정렬하는 기법(사전식 정렬 방법)

• 정렬하고자 하는 값을 버킷에 넣어 정렬

• 버킷으로 큐 사용

• 데이터가 입력되는 곳, 출력되는 곳 : 먼저 들어온 것이 먼저 출력

• 버킷의 개수는 키의 표현 방법과 밀접한 관계

  • 이진법을 사용한다면 버킷은 2개
  • 알파벳 문자를 사용한다면 버킷은 26개
  • 십진법을 사용한다면 버킷은 10개

• 기수 정렬 방법

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

• 키의 가장 큰 자리수까지 반복 수행

• 한 자리 수의 기수 정렬 수행 예

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