기수 정렬은 정수 배열을 입력받아 각 숫자의 기수(즉, 자릿수)를 기준으로 정렬하는 알고리즘이다. 이때, 정렬 서브루틴으로 종종 다른 효율적인 정렬 알고리즘을 사용한다. 기수 정렬에서 일반적으로 사용되는 서브루틴으로는 계수 정렬(Counting Sort)과 버킷 정렬(Bucket Sort)이 있다.
이 알고리즘의 첫 번째 단계는 정렬에 사용할 “기수” 또는 진법을 정의하는 것이다. 이 예제에서는 10진수를 다루므로 기수를 10으로 설정한다.
다음 단계는 간단히 n번 반복하는 것이다. 여기서 n은 입력 배열에서 가장 큰 정수의 자릿수다. 각 반복마다 현재 자릿수에 대해 정렬 서브루틴을 수행한다.
예제로 사용할 입력 배열을 살펴보자.
배열에서 가장 큰 정수는 802이고, 이 숫자는 세 자리수(일의 자리, 십의 자리, 백의 자리)를 가지고 있다. 따라서 알고리즘은 각 정수의 자릿수에 대해 정렬을 수행하며 총 세 번 반복된다.
더 자세한 내용은 위키피디아를 참고하자.
Swift Algorithm Club의 Christian Encarnacion이 작성