비교하지 않는 정렬의 마법

// 1. 자릿수 가져오기 (수학적 트릭 사용)
function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

// 2. 자릿수 세기
function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

// 3. 최대 자릿수 찾기
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); // 가장 긴 녀석이 4자리면 4번 돔

  for (let k = 0; k < maxDigitCount; k++) {
    // 10개의 빈 바구니 생성 (0 ~ 9)
    let digitBuckets = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < nums.length; i++) {
      // k번째 자릿수를 알아내서 해당 바구니에 넣는다 (Push)
      let digit = getDigit(nums[i], k);
      digitBuckets[digit].push(nums[i]);
    }

    // 바구니에 담긴 숫자들을 순서대로 다시 합친다 (Concat)
    // [].concat(...digitBuckets)와 같음
    nums = [].concat(...digitBuckets);
  }

  return nums;
}

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