[Udemy] 지수 정렬(Radix sort)이란?

 

정의

지수정렬은 비교 정렬이 아닌 특수한 정렬 방법이다.

이진법이든 십진법이든 정수 정렬에서만 수행된다.

A가 B보다 큰지 작은지 비교하는 것이 아닌 자릿수를 통해서 정렬한다.

 

 

접근

각 자리수를 버켓(bucket)에 담는다. 버켓에 담긴 낮은 숫자순으로 아래에서부터 재배열한다.

이를 최대 자릿수까지 반복하여 모두 진행하면 결과가 나타난다.

 

1. 자릿수를 구하는 함수가 필요하다.

2. 몇번 반복해야하는지 알기 위해 최대 자릿수를 알아내야한다.

3. 최대 자리수만큼 반복하면서 버켓에 담긴 자릿수를 다시 배열로 정렬하여 마지막 결과값을 반환한다.

 

 

코드

1. helper 메소드

주어진 정수의 자릿수에 위치한 숫자를 구하는 함수가 필요하다.

그래야 버켓에 원하는 위치에 추가할 수 있기 때문이다.

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]))
    }

    return maxDigits;
}

 

digitCount로 숫자의 자릿수를 구하고 mostDigits로 주어진 배열 중 최대 자릿수를 구한다.

 

2. radixSort 구현

function radixSort(arr) {
    let maxDigit = mostDigits(arr)

    for (let i = 0; i < maxDigit; i++) {
        let bucket = Array.from({length:10}, () => []);
        for (let j = 0; j < arr.length; j++) {
            bucket[getDigit(arr[j], i)].push(arr[j])
        }
        arr = [].concat(...bucket)
    }
    return arr;
}

 

mostDigits로 최대자릿수를 구한 만큼 반복문을 순회한다.

이 때 버켓을 생성하고 배열의 모든 요소를 순회하여

버켓에 추가해야하므로 중첩 반복문을 순회한다.

 

 

첫번째 자릿수에서 버켓의 모든 요소가 추가되면,

arr(인자)에 현재 버켓에 들어있는 순서대로 정렬한 배열을 할당한다.

이를 최대 자릿수까지 반복한 후 arr(인자)를 반환한다.

 

시간복잡도

 

시간 복잡도는 O(nk)이다. 

n은 정수의 수, k는 정수들의 자릿수이다.

즉, 자릿수가 매우 긴 수라면 시간 복잡도가 증가할 수 있다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의