기수 정렬 (Radix Sort) 설명과 JavaScript 예제

기수 정렬(Radix Sort)은 자릿수를 기준으로 정렬하는 비교 기반이 아닌 정렬 알고리즘입니다. LSD(Least Significant Digit) 방식과 MSD(Most Significant Digit) 방식이 있으며, 일반적으로 자릿수 낮은 곳부터 정렬하는 LSD 방식이 많이 사용됩니다. 정수가 많고 자릿수가 제한된 경우 매우 빠른 성능을 발휘합니다.

---

1. 동작 원리 (LSD 방식 기준)

1. 모든 숫자의 1의 자리부터 시작해 자릿수별로 정렬
2. 10개의 큐(0~9)를 만들어 해당 자릿수의 숫자에 따라 분배
3. 자릿수를 한 칸씩 올려가며 반복
4. 가장 높은 자릿수까지 정렬하면 전체가 정렬됨

→ 내부적으로는 안정 정렬이 반복되어 수행됩니다.

---

2. JavaScript 예제 - 오름차순 정렬

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

function digitCount(num) {
  return num.toString().length;
}

function mostDigits(nums) {
  return Math.max(...nums.map(digitCount));
}

function radixSort(nums) {
  const maxDigit = mostDigits(nums);

  for (let k = 0; k < maxDigit; k++) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < nums.length; i++) {
      const digit = getDigit(nums[i], k);
      buckets[digit].push(nums[i]);
    }
    nums = [].concat(...buckets);
  }

  return nums;
}

console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));
// [2, 24, 45, 66, 75, 90, 170, 802]

• getDigit: 특정 자릿수의 숫자 추출
• digitCount: 숫자의 총 자릿수 계산
• radixSort: 각 자릿수마다 0~9로 분류하여 정렬 반복

---

3. 성능 분석

구분	시간 복잡도
최선/평균/최악	O(nk)

• n: 배열 길이, k: 최대 자릿수
• 공간 복잡도: O(n + k)
• 안정 정렬 (같은 값의 순서가 유지됨)

---

4. 기수 정렬의 특징

• 정수 정렬에만 사용 가능 (음수/실수는 별도 처리 필요)
• 비교 연산을 하지 않음 → 큰 장점
• 자릿수 작은 데이터에 매우 빠름

---

마무리

기수 정렬은 단일 비교 없이도 빠른 정렬이 가능한 독특한 알고리즘입니다. 정수 데이터가 많고 범위가 제한적일 때 매우 유용하며, 일부 정렬 라이브러리나 내부 구현에서도 활용되기도 합니다.

배열이 크고, 자릿수 범위가 작을수록 기수 정렬의 성능이 돋보입니다.