[알고리즘] 기수정렬

1. 기수정렬 방법

기존 정렬과는 다르게 숫자의 크기를 비교하지 않는다.

하지만 정렬할때 사용할 실제 데이터는 숫자여야 한다.

비교하는 대신 숫자크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한다.

이 말의 의미는 자릿수가 더 큰수가 더 크다는 것이다.

 

2. 헬퍼 메소드

자릿수 알아내기, 수와 위치를 가져온 다음 그 위치의 숫자를 반환한다.

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;
}

3. 기수정렬 코드

(1) 수 목록을 받는 함수를 정의

(2) 가장큰수가 몇자리 인지 알아내기

(3) 진행할때마다 각 자릿수에 버킷 만들기(0~9)

(4) 버킷은 빈배열이다.

function radixSort(nums) {
  let maxDigitCount = 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;
}

4. 기수정렬 빅O

숫자의 자리수가 매우 커지면 영향을 미치므로 O(n)이 아닌 O(nk) 로 한다.

기수정렬의 빅O는 논란이 되는 부분도 있다고 한다.

숫자를 정렬할때 모든수가 고유하고 무작위로 분산된 데이터를 다룰경우에는 k값이 logn이 된다.

그 이유는 컴퓨터가 숫자, 정보를 저장하는 방식 때문이라고 한다.

 

결론 : 이론적으로 기수정렬은 모든 비교정렬보다 빠를수 있다.

하지만 컴퓨터 메모리에 수를 저장하는 방식에 대한 제한으로 인해 실제로는 그렇지 않고 비교정렬과 비슷할 수도 있다.