3.8Radix Sort

Radix Sort

Radix란 수학에서 밑 또는 기수를 뜻한다. 예를 들어 2진법은 기수가 2, 10진법은 기수가 10이다.

Radix Sort(기수 정렬)는 숫자의 자릿수를 기준으로 정렬하는데, 비교 연산을 사용하지 않고 정렬이 가능하다.

기수 정렬은 기본적으로 다음과 같은 아이디어를 바탕으로 한다:

1. 모든 숫자들 중 가장 큰 자릿수(k)를 구한다.
2. 1의 자리부터 시작해 k번째 자릿수까지 다음의 정렬을 반복한다:
3. 매 자릿수마다 0 ~ 9까지의 버킷을 만들고, 해당 자릿수에 어떤 값이 있는지에 따라 숫자를 버킷에 분류한다.
4. 0 ~ 9로 나뉘어진 버킷들을 쭉 이어 붙이면 해당 자릿수는 정렬된 상태가 된다. k번째 자릿수까지 반복한다.

Helper Method들 만들기

• 우선, 1단계의 배열에서 가장 큰 자릿수가 몇인지 세는 함수를 작성하기 위해 자릿수가 몇개인지 세는 함수를 작성해보자. 밑이 10인 로그 Math.log10(n)로 쉽게 구할 수 있다.

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

다음으로,

• 배열에서 가장 큰 자릿수가 몇인지 세는 함수는 아래와 같이, 앞서 작성한 digitCount를 활용한 루프문으로 작성할 수 있다.

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

• 또, 분류하고자 하는 수의 i번째 자릿수에 있는 수를 구하는 함수는 아래와 같이 작성할 수 있다.

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

Radix Sort 구현하기

javascript
function radixSort(nums){
  const mostDigitCount = mostDigits(nums);
  for(let k = 0; k < maxDigitCount; k++){
    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]);
    }
    nums = [].concat(...digitBuckets);
  }
  return nums;
}

Radix Sort의 Big O

기수 정렬의 시간 복잡도는 늘 O(nk)이다. 여기서 n은 배열의 길이, k는 배열에 있는 수의 최대 자릿수이다. 즉, 최대 자릿수가 아주 클수록 기수 정렬의 성능은 악화된다. 만약 k가 n만큼이나 크다면 O(n²)이 걸릴 수 있다.

따라서 다른 빠른 정렬들이 O(n log n)이 걸리는 것을 감안하면 k가 log n보다 작을때 기수 정렬은 아주 좋은 선택이 될 수 있다. 많은 경우에서 수의 자릿수는 아주 크지 않기 때문에, 이럴때 기수 정렬은 정렬 시간을 O(n)으로 만들 수 있다!

반면 기수 정렬의 공간 복잡도는 O(n + k)이다. 우선 정렬할 항목의 수가 n개이면 각 자릿수별 정렬 단계에서 n개를 버킷에 저장해야하므로 O(n), 또 k번 루프를 반복하므로 O(k)를 더하게 된다.

---

🤠 개인 탐구

공간 복잡도 O(n + k)

개인적으로는 공간 복잡도에 왜 n이 들어가는지 이해하기 어려웠습니다. n개의 요소가 있는 배열이 주어지면 공간 복잡도는 O(1)인데, 기수 정렬은 10개의 버킷이 있고 각각의 버킷은 배열이기 때문에 O(1), 즉 10개면 O(10) = O(1)이 아니냐는 거죠.

이 부분은, 공간 복잡도의 기준, 즉 공간 복잡도를 어떻게 측정하기로 합의했는지 정확히 이해하지 못해서 생기는 오해였습니다. 공간 복잡도는 입력(즉, 처음에 주어진 사용 메모리)이 아니라, 추가로 사용하는 메모리가 기준입니다.

기수 정렬에서, n개의 요소를 10개의 버킷에 모두 담는데 그러면 버킷 10개를 다 합치면 n개의 요소를 모두 담을 수 있는 추가적인 공간이 필요하게 됩니다. 따라서 이 추가적인 메모리 공간을 O(n)이 필요한 것으로 말할 수 있습니다.

결론적으로, 이미 주어진 입력 외에 알고리즘이 추가로 사용하는 메모리의 양을 분석하는 것이 공간 복잡도이기 때문에 기수 정렬은 O(n + k)의 메모리를 쓴다고 할 수 있습니다.