기수 정렬(Radix Sort)은 숫자의 자릿수, 즉 기수(radix)를 기준으로 정수들을 버킷(bucket)에 분배하여 정렬하는 알고리즘입니다. 비교 연산 없이 자릿수를 단계적으로 검사하며 정렬하기 때문에, 데이터가 특정 조건(정수 등)을 만족할 때 매우 효율적인 성능을 보여줍니다. 기수는 배열 값들이 사용하는 진법 체계(10진수라면 0~9)에 따라 결정됩니다.
동작 원리
기수 정렬은 다음과 같은 과정으로 동작합니다.
1. 배열에서 최댓값을 찾아 정렬이 필요한 최대 자릿수를 파악합니다.
2. 가장 낮은 자릿수(1의 자리)부터 시작하여 각 숫자를 해당 자릿수 값에 맞는 버킷에 분배합니다.
3. 버킷을 순서대로 연결(concatenate)하여 배열을 재구성합니다.
4. 다음 자릿수(10의 자리, 100의 자리...)로 이동하며 위 과정을 반복합니다.
5. 모든 자릿수에 대한 처리가 끝나면 정렬이 완료됩니다.
자바스크립트 구현 예제
function radixSort(arr) {
// 최댓값을 찾고 10을 곱해 최댓값의 자릿수 + 1 크기의 수를 만듭니다
const maxNum = Math.max(...arr) * 10;
let divisor = 10;
while (divisor < maxNum) {
// 0~9 각각에 대응하는 버킷 배열을 생성합니다
let buckets = [...Array(10)].map(() => []);
// 각 숫자의 현재 유효 자릿수를 구해 해당 버킷에 넣습니다
for (let num of arr) {
buckets[Math.floor((num % divisor) / (divisor / 10))].push(num);
}
// 모든 하위 배열을 연결하여 배열을 재구성합니다
arr = [].concat.apply([], buckets);
// 다음 자릿수로 이동합니다
divisor *= 10;
}
return arr;
}
console.log(radixSort([5,3,88,235,65,23,4632,234]))실행 결과
[ 3, 5, 23, 65, 88, 234, 235, 4632 ]
코드 설명
divisor 변수는 현재 처리 중인 자릿수를 나타냅니다. 처음에는 10으로 시작하고, 루프가 반복될 때마다 10씩 곱해져 10의 자리, 100의 자리 순으로 확장됩니다. (num % divisor) / (divisor / 10) 연산을 통해 특정 자릿수의 값을 추출할 수 있으며, 이 값이 바로 해당 숫자가 들어갈 버킷의 인덱스가 됩니다.
예를 들어 4632에서 divisor가 10일 때는 1의 자리인 2를 추출해 2번 버킷에 넣고, divisor가 100일 때는 10의 자리인 3을 추출해 3번 버킷에 넣는 방식입니다. 이러한 과정을 최대 자릿수만큼 반복하면 안정적으로 정렬된 배열을 얻을 수 있습니다.
시간 복잡도
기수 정렬의 시간 복잡도는 O(d × (n + b))입니다. 여기서 n은 요소의 개수, b는 기수(진법), d는 최댓값의 자릿수를 의미합니다. 자릿수가 고정된 정수 데이터의 경우 사실상 선형 시간에 가까운 성능을 보이지만, 음수나 소수처럼 다양한 형태의 수를 다룰 때는 추가 처리가 필요하다는 점을 유의해야 합니다.