기수 정렬(Radix Sort)

특징

• 진법의 기준이 되는 수를 기수(Radix)라고 합니다. (예: radix-2: 2진, radix-10: 10진)
• 비교를 통한 정렬이 아닙니다.
• 분배 후 순차적으로 꺼내는 방식으로 정렬됩니다.
• 문자열과 정수에는 적용 가능하지만 부동소수점 숫자에는 적용 불가능합니다. 즉, 소수점을 가진 숫자들의 배열에는 적용할 수 없습니다. (자릿수가 없기 때문에)

절차

1. 빈 배열을 10개 가진 배열을 만듭니다.(버킷)
2. 첫 번째 자릿수에 해당하는 버킷에 원소들을 넣습니다.
3. 모든 원소를 버킷에 넣고나면 작은 숫자의 버킷에서부터 순서대로 원소들을 정렬합니다.
4. 가장 큰 숫자의 자릿수만큼 2, 3번 과정을 반복합니다.

효율

• 시간복잡도
  • O(N)
  • 최선, 최악, 평균적인 경우 모두 같은 시간복잡도를 가집니다. 
• 공간복잡도
  • O(N)

구현

// 최대 자릿수 얻는 함수
let getMaxDigitCount = function(array) {
    let result = 0;
    for (let num of array) {
        result = Math.max(result, num.toString().length);
    }
    return result;
}

// 각 자릿수 얻는 함수
let getDigit = function(num, i) {
    let result = (Math.floor(num % (10 ** (i + 1))) - Math.floor(num % (10 ** i))) / (10 ** i);
    return result;
}

let radixSort = function(array) {
    // 분배에 사용할 버킷을 만든다.
    let bucket = [];
    while (bucket.length < 11) {
        bucket.push([]);
    }
    // 분배-정렬의 반복 횟수를 얻는다.
    let loopCount = getMaxDigitCount(array);
    for (let i = 0; i < loopCount; i++) {
        while (array.length) {
            // 자릿수에 해당하는 버킷에 넣는다.
            let num = array.shift();
            bucket[getDigit(num, i)].push(num);
        }
        // 0번 버킷부터 순서대로 빼내서 정렬한다.
        for (let k = 0; k < 10; k++) {
            while (bucket[k].length) {
                array.push(bucket[k].shift());
            }
        }
        console.log(...array);
    }
}

let sample = [125, 383, 274, 96, 0, 9, 81, 72];
radixSort(sample);

/* 정렬 과정 출력
0 81 72 383 274 125 96 9
0 9 125 72 274 81 383 96
0 9 72 81 96 125 274 383
*/