기수 정렬 (Radix Sort)

기수가 무엇인가 ?

• [ ] 숫자를 나타낼 때 사용하는 “자리”의 기본 단위를 의미한다. → 즉, 숫자의 각 자리에서 사용되는 값의 범위를 말한다 ! ( ex: 10진법에서의 기수는 10(0~9), 2진법에서의 기수는 2(0, 1) )

기수 정렬 ?

• [ ] 비교 기반이 아닌 정렬 알고리즘 중 하나로, 수의 각 자리수를 기준으로 순차적으로 정렬하는 방식이다. → 주로 정수나 문자열과 같은 자료에서 사용된다.
• [ ] 일반적으로 자릿수가 작고 데이터의 범위가 넓을 때 적합한 알고리즘이다 !
• [ ] 기수 정렬은 자리수별로 데이터를 정렬하고, 그 결과를 누적하여 전체 데이터를 정렬하게 된다.
  1. LSD (Least Significant Digit) 방식
  2. MSD (Most Significant Digit) 방식

LSD 기수 정렬

• [ ] 이 방식은 수의 가장 오른쪽(가장 낮은 자리수)부터 왼쪽(가장 높은 자리수)으로 순차적으로 정렬하는 방식이다. ( 일반적으로 사용되는 방식 ! )
• [ ] 각 자리수에 대해 안정 정렬(Stable Sort)을 사용해야 한다. → 같은 자리에서 값이 같은 경우, 기존의 순서를 유지해야 최종 정렬이 올바르게 이뤄지기 때문에 !

<aside> 💡

안정 정렬 ?

• 동일한 값들이 배열에 등장할 경우, 원래 순서를 유지하면서 정렬하는 것을 말한다. ( ex: 계수 정렬(Counting Sort) ) </aside>