[정렬 알고리즘]비교를 수행하지 않는 Radix Sort

지금까지 정리한 정렬들은 비교 정렬 알고리즘이다. 버블 정렬에 대해 다루거나, 더 발전된 퀵 정렬을 다루더라도 결국 본질적으로 기본 비교는 주어진 시점에서 두 개의 항목을 비교한다. 주어진 시간에 비교하는 최대량이다.

Bubble Sort - O(n^2), Insertion Sort - O(n^2), Selection Sort - O(n^2)

개선된 정렬 비교 알고리즘. Quick Sort - O(n log n), Merge Sort - O(n log n)

더 빠른 정렬 알고리즘이 있을까? Yes, 하지만 비교를 통해서는 아니다.

수학적으로 제한이 있기에 비교 정렬의 기대할 수 있는 최상의 시간 복잡도는 n log n이다. 

기수 정렬 - Radix Sort

• 비교를 수행하지 않는 특별한 정렬 알고리즘이고, 숫자로 동작한다.
• 두 요소를 가지고 비교하지 않는다.
• 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한다. 이 말의 의미는 자릿수가 더 큰 수, 예를 들어 네 자릿수가 있다면 두 자릿수보다 큼.  두 수를 비교하진 않지만, 자릿수가 더 많은 수가 더 적은 수보다 크다는 것을 알고 있다. 

작동 방식

정렬하려고 하는 수 목록 십인수인 한 자리, 두 자리, 세 자리, 네 자릿수가 있다. 열개의 각기 다른 버킷을 만든다.

이러한 버킷은 기수가 10인 한 자리 수로 가능한 모든 숫자를 나타낸다. 오른쪽에서 첫 번째 자릿수를 기준으로 버킷에 분류한다. 가장 오른쪽의 숫자만 살펴본다. 

버킷 안에서는 정렬하지 않으며 여기 분류된 순서를 유지하면서 다시 목록을 구성한다. 

다음 자릿수로 가서 이 과정을 다시 실행한다.

이제 오른쪽에서 두 번째 자리의 숫자를 이용해 그룹으로 묶은 모습이다. 한 자리 수 같은 경우 해당 위치에 숫자가 없으니 0번 버킷에 넣었다. 

진행할 때마다 점점 완성해 가고 있다. 수를 다른 수와 비교하지 않았다. 세 번째 숫자에 대해 다시 반복한다.

작은 수는 이미 0 그룹으로 묶여 있다. 

다시 목록으로 구성한 다음 한 번 더 해야한다. 이 과정을 실제로 수행해야 할 횟수는 가장 큰 수의 자릿수에 달려 있다는 것을 알 수 있다. 

목록으로 다시 구성한다. 목록으로 다시 구성한다는 것은 버킷에 이미 있는 순서로 둔다는 뜻이다. 4부터 시작하여

902까지 가는 거다.

숫자가 정렬되었다. 애니메이션으로도 살펴보자.

7진수를 다룬다면 버킷이 7개가 된다. 

Radix Sort Helpers

메인 알고리즘을 실제로 작성할 수 있도록 몇가지 헬퍼 메서드가 필요하다.

 

getDigit(num, place) - 수와 위치(자릿수)를 가져온 다음 그 위치의 숫자를 반환한다. 

✅ 먼저 알고 넘어가기
Math.pow(base, exponent) - base^exponent처럼 base에 exponent를 제곱한 값을 반환한다. 
Math.abs(x) - 숫자의 절대값을 반환한다. ex) Math.abs(-1) //1
Math.floor(x) - 항상 내림하고, 주어진 숫자보다 작거나 같은 가장 큰 정수를 반환한다. ex) Math.floor(5.95) //5

function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

getDigit(7323, 2)을 실행한다고 했을 때, Math.pow(10, 2) 이므로 100이 나온다. 그러고 7323을 100으로 나눈다.

73.23이 될테고 내림(floor)하면 73이 된다. 10으로 나눌 때의 나머지를 구하니 3이 된다. 

 

주어진 숫자 목록에 몇 번 실행해야 할지 알아낼 코드를 작성해야 한다. 해야 할 일은 가장 큰 숫자에 자릿수가 얼마나 되는지 알아내야 한다. 

digitCount(num) - 하나의 수에 대한 자릿수를 반환한다. 

✅ 먼저 알고 넘어가기
Math.log10(x) - 숫자의 밑이 10인 로그를 반환한다. 10을 몇 번 제곱해야 x를 얻을 수 있는지에 대한 답이다.

function digitCount(num) {
    if (num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num))) +1;
}

대부분 딱 떨어지는 수가 아니기에 내림(floor)을 하는 것이고, Math.log10(423) = 2.3263... 이며 내림하면 2이다. 해당 수에 +1 하여 자릿수를 구하게 된다. Math.log10(0)을 수행하려 하면 -Infinity를 얻기에 조건을 추가하였다. 

 

mostDigits(num) - 수 목록을 가져와서 자릿수가 가장 큰 수의 자릿수를 반환한다.

✅ 먼저 알고 넘어가기
Math.max() - 입력값으로 받은 0개 이상의 숫자 중 가장 큰 숫를 반환.
매개변수를 제공하지 않는 경우 -Infinity, 한 개 이상의 요소가 숫자로 변환되지 않는다면 NaN

function mostDigits(nums) {
    let maxDigits = 0;
    for (let i = 0; i < nums.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(nums[i]));
    }
    return maxDigits;
}

의사코드

• 수 목록을 받는 함수를 정의한다.
• 가장 큰 수가 몇 자리인지 알아낸다. 
• 0부터 가장 큰 자릿수까지 반복한다.
  • loop가 진행될 때마다 각 자릿수에 버킷을 만든다. [[],[],[]...] 형태의 10개의 하위 배열 존재
  • 각각의 수를 올바른 버킷에 넣는다. 
• 기존 배열을 버킷의 값(0부터 9까지)으로 교체한다. 
• 목록을 반환한다.

4자리 수라면 네 번 수행되는 외곽 루프가 있고, 목록의 각 수에 무언가 수행하려면 내부 루프가 필요하다.

function radixSort(nums) {
    // 가장 큰 수가 몇자리인지 알아냄.
    let maxDigitCount = mostDigits(nums);
    // 최대 자릿수만큼 반복
    for (let k = 0; k < maxDigitCount; k++) {
        // 배열안에 10개의 빈 배열 생성
        let digitBuckets = Array.from({length: 10}, () => []);
        for (let i = 0; i < nums.length; i++) {
            let digit = getDigit(nums[i], k);
            digitBuckets[digit].push(nums[i])
            // Bucket안에 올바른 index 값에 숫자 넣음.
            // digitBuckets[getDigit(nums[i], k)].push(nums[i]);
        }
        // digitBuckets에 있는 배열을 풀어서 새 배열로 구성
        nums = [].concat(...digitBuckets)
    }
    return nums
}

radixSort([23, 345, 5467, 12, 2345, 9852])

Radix Sort Big O

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

n은 정렬할 항목 수나 정수의 수이고, k는 수의 길이(자릿수)이다. 자릿수가 길다면 이 점을 고려해야 한다.

이론적으로, 기수 정렬은 모든 비교 정렬보다 빠를 수 있지만 컴퓨터 메모리에 수를 저장하는 방식에 대한 제한으로 인해 실제로는 그렇지 않을 수 있으며, 비교 정렬과 마찬가지일 수 있다.