기수정렬 (Radix Sort)

기수정렬
기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.
가장 큰 자릿수를 D라고 했을 때 0(DN)의 시간 복잡도를 가진다

=>기수 정렬을 사용하기 위해선 데이터의 값들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다.

 

📌num의 i번째 자리에 있는 수를 반환  코드

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

 

📌num의 자리 수를 반환 코드

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

 

🧩이중 반복문을 통한 기수정렬

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

function radixsort(nums) {
//가장큰 자리수 만큼 반복문 돌리기
  let maxDigitCount = mostDigits(nums);
  for (let k = 0; k < maxDigitCount; i++) {
  //별도의 메모리 공간 만들기
    let digitbuckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < nums.length; i++) {
    //i번째 자리에 있는 수를 가져와서 키값으로 만들어준다 
      let digit = getDigit(nums[i], k);
    // digit번째의 메모리공간에 값을 넣어준다 
      digitbuckets[digit].push(nums[i]);
    }
    nums = [].concat(...digitbuckets);
  }
  return nums;
}