기수 정렬(Radix Sort)이란?
기수 정렬은 정수 키를 가진 데이터를 정렬하는 비교 기반이 아닌 알고리즘입니다. 숫자를 일의 자리, 십의 자리, 백의 자리처럼 각 자릿수별로 나누어, 같은 자릿수와 값을 공유하는 키끼리 그룹(버킷)으로 묶는 방식으로 정렬을 수행합니다.
비교 연산 없이 자릿수만 반복적으로 확인하기 때문에, 데이터 범위가 적절한 경우 매우 빠른 성능을 보여줍니다. 시간 복잡도는 O(d × (n + b))로, 여기서 d는 최대 자릿수, n은 요소 개수, b는 진법(기수)입니다.
구현 목표
리터럴 값으로 이루어진 배열 하나를 인수로 받아, 기수 정렬 알고리즘을 사용해 배열을 오름차순 또는 내림차순으로 정렬하는 자바스크립트 함수를 작성해야 합니다.
예제 코드
다음은 기수 정렬을 구현한 코드입니다.
const arr = [45, 2, 56, 2, 5, 6, 34, 1, 56, 89, 33];
const radixSort = (arr = []) => {
const base = 10;
let divider = 1;
let maxVal = Number.NEGATIVE_INFINITY;
while (divider === 1 || divider <= maxVal) {
// 각 자릿수(0~9)에 해당하는 버킷 생성
const buckets = [...Array(10)].map(() => []);
for (let val of arr) {
// 현재 자릿수 값을 기준으로 버킷에 분배
buckets[Math.floor((val / divider) % base)].push(val);
maxVal = val > maxVal ? val : maxVal;
}
// 버킷 순서대로 다시 합침
arr = [].concat(...buckets);
divider *= base;
}
return arr;
};
console.log(radixSort(arr));
코드 동작 원리
- 버킷 초기화: 0부터 9까지 총 10개의 빈 배열(버킷)을 만듭니다.
- 자릿수 추출:
(val / divider) % base계산을 통해 현재 검사 중인 자릿수의 숫자를 얻습니다. divider가 1일 때는 일의 자리, 10일 때는 십의 자리를 의미합니다. - 분배 후 병합: 각 숫자를 해당 자릿수 버킷에 넣은 뒤, 버킷 순서대로 이어 붙여 새로운 배열을 만듭니다.
- 반복 종료 조건: divider가 배열 내 최댓값(maxVal)보다 커지면 모든 자릿수를 처리한 것이므로 루프를 종료합니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[
1, 2, 2, 5, 6,
33, 34, 45, 56, 56,
89
]
입력 배열이 중복 값(2, 56)을 포함하더라도 안정적으로 처리되어 올바르게 오름차순 정렬된 것을 확인할 수 있습니다.