How it works?

기수 정렬(Radix Sort)은 가장 낮은 자릿수(일의 자리)부터 가장 높은 자릿수까지 한 번에 한 자릿수씩 처리합니다. 각 단계에서는 안정(stable) 정렬을 사용하므로 이전 단계에서 수행된 정렬 순서가 보존됩니다.

단계별 프로세스:

1. 안정 계수 정렬(stable counting sort)을 사용하여 일의 자릿수를 기준으로 정렬합니다.
2. 동일한 값에 대해 이전 순서를 유지하면서 십의 자릿수를 기준으로 정렬합니다.
3. 가장 큰 수의 자릿수까지 모두 처리할 때까지 백의 자리, 천의 자리 등으로 계속 진행합니다.

[170, 45, 75, 90, 2, 802, 24, 66]에 대한 예시:

• 일의 자릿수 기준: [170, 90, 2, 802, 24, 45, 75, 66]
• 십의 자릿수 기준: [2, 802, 24, 45, 66, 170, 75, 90]
• 백의 자릿수 기준: [2, 24, 45, 66, 75, 90, 170, 802]

마지막 자릿수까지 마치면 배열이 완전히 정렬됩니다. 핵심은 높은 자릿수를 정렬하는 동안 안정성(stability) 덕분에 낮은 자릿수의 순서가 그대로 유지된다는 점입니다.