[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 17: 기수 정렬)

섹션 17: 기수 정렬

버블, 선택, 삽입, 합병, 퀵 정렬은 비교 정렬에 속한다. 반면 기수 정렬은 정렬할 숫자를 비교하지 않고 bucket이라는 10개의 배열(0~9)에 담았다가 병합하는 방식으로 정렬한다. 이렇게 bucket에 담았다가 병합하는 과정은 정렬할 숫자의 최대 자릿수만큼 일어난다. 

// 자릿수에 해당하는 숫자 반환
function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i) % 10);
}

// 숫자의 자리수 세기
function digitCount(num) {
    if (num === 0) return 1;
    // log 계산은 지수와 밑이 같으면 1이다.
    // 지수가 10이기 때문에 두자리 수인 10은 1이된다. 여기에 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]))
    }
    return maxDigits;
}

function radixSort(nums) {
    let maxDigitCount = mostDigits(nums);
    for(let k = 0; k<maxDigitCount; k++) {
        let digitBuckets = Array.from({length: 10}, () => []) // 10진수의 한 자릿수는 0~9이기 때문
        for (let i = 0; i<nums.length; i++) {
            let digit = getDigit(nums[i], k);
            digitBuckets[digit].push(nums[i]);
        }
        nums = [].concat(...digitBuckets); // 병합
    }
    return nums;
}

console.log(radixSort([23, 345, 5678, 12, 2345, 9852]));

 

Big O

n은 정렬할 정수의 개수이고, k는 정수의 자릿수이다.

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Radix Sort	O(nk)	O(nk)	O(nk)	O(n+k)