[알고리즘] 기수정렬 (자바스크립트)

앞서 학습한 버블정렬, 선택정렬, 삽입정렬, 합병정렬, 퀵정렬은 '비교 정렬' 그룹에 속함. 주어진 시간에 두 가지 요소를 비교하는 방식. 이러한 비교 정렬은 한계점이 존재하며, 최선의 경우 O(n log n)의 복잡도를 갖는다 (합병정렬, 퀵정렬)

 

기수정렬 (Radix Sort)

비교를 수행하지 않는 특별한 정렬 알고리즘으로, 숫자 크기에 대한 정보를  이진수로 인코딩하여 정렬한다.

 

작동방식

배열 요소의 0의 자리 수부터 분리한다. 모든 값들은 (0-9) 사이로 레이블링되고, 이를 0 레이블의 먼저 들어온 값부터 꺼내 배열한다. 자릿수를 좌측으로 옮겨가며 레이블링을 반복하면, 정렬이 완료된다.

 

헬퍼함수

1. getDigit(원하는 숫자 인덱스 찾기) : 원하는 숫자가 어느 자릿수 인덱스에 위치하는지 반환한다. 기존의 숫자 인덱스 파싱과 차이점이 있다면, 오른쪽부터 카운트한다는 점이다.

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

 

2. digitCount(자릿수 알아내기)

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

 

3. mostDigit(숫자 배열 중 가장 긴 요소의 자릿수 알아내기)

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

 

의사코드

1. 숫자 배열을 입력으로 받는 함수 선언
2. 루프 횟수 확인을 위해 숫자 배열에서 가장 큰 수의 자릿수를 저장, 0부터 해당 자릿수까지 레이블링 반복
3. 레이블링 결과를 자릿수마다 빈 배열(버킷)에 쌓고, 기존 배열을 버킷의 순서로 교체

 

구현

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

 

정리

정렬을 위한 헬퍼 메서드의 로직만 이해한다면, 이를 모듈처럼 조립하면 되기 때문에 어렵지 않게 구현할 수 있었다. 특별한 점이라 한다면 버킷에 담긴 숫자 배열들을 Nums에 합칠 때 Spread Operator를 사용한다는 것인데, 입력받았을 때의 차원을 반환할 때도 유지하기 위함인 듯 하다.

 

기수 정렬의 시간 복잡도는 언제나 O(nk) 이다. 여기서 n은 입력받은 배열 요소의 갯수,k는 자릿수를 뜻한다. 상수 곱은 크게 보면 일반적으로 O(n)이지만, 자릿수가 일반적인 상수 곱보다 큰 영향을 미치기 때문에, 이와 같이 표기한다.