앞에까지 정렬은 비교 정렬 알고리즘.
기수 정렬은 비교를 수행하지 않는다.
숫자로 작동되며 이진수를 사용한다.
https://visualgo.net/en/sorting
숫자만 가능하며 숫자를 옆에 것과 1:1 로 비교하지 않고
1의 자리만 보고 1-9까지 버켓에 담고, 그 순서대로 다시 배열을 만들고
10의 자리만 보고 동일한 작업을 수행한다. 반복.
가장 큰 수의 자릿수까지 반복하면 결국 모든 정수는 순서대로 정렬된다.
먼저 자릿수를 가져오는 헬퍼 함수를 만든다.
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
다음으로 수에 자릿수가 얼마나 되는지 리턴하는 함수를 만든다.
function digitCount(num) {
if(num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
수 목록에서 최대 자릿수를 구하는 함수를 만든다.
function mostDigits(nums) {
let maxDigits = 0;
for(let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i])); // 위에 작성한 digitCount 함수를 활용한다.
}
return maxDigits;
}
앞에 3개의 헬퍼 함수를 가지고 기수 정렬을 구현한다.
function radixSort(nums){
let maxDigitCount = mostDigits(nums); // 배열에서 가장 큰수의 자릿수.
for(let k = 0; k < maxDigitCount; k++){ // 그 자릿수까지 루프 돌림
let digitBuckets = Array.from({length: 10}, () => []); // 빈배열 10개로 된 배열 생성. 버켓.
for(let i = 0; i < nums.length; i++){ // 배열의 처음부터 끝까지 루프
let digit = getDigit(nums[i],k); // k자릿수의 값을 나타냄.
digitBuckets[digit].push(nums[i]); // 해당 자릿수의 숫자 버켓에 담긴다.
}
nums = [].concat(...digitBuckets); // 스프레드 연산자를 쓰면 배열 속 배열까지 하나의 배열로 합쳐짐.
}
return nums;
}
radixSort([23,345,5467,12,2345,9852])
최선의 경우 → O(nk)
최악의 경우 → O(nk)
평균의 경우 → O(nk)
공간복잡도 → O(n + k)
n은 정렬한 항목 수나 정수의 수,
k는 이러한 수의 길이. 만약 아주아주 긴 수가 있다면 시간에 영향을 크게 준다.
기수정렬의 빅오에 대해 약간의 논란이 있다.
이론적으로 기수 정렬은 모든 비교 정렬보다 빠를 수 있다.
그러나 메모리에 수를 저장하는 방식에 대한 제한으로 인해 실제로는 느릴 수 있다.