Udemy - 지수 정렬

---

지수 정렬이란?

이전까지 공부했던 정렬들은 모두 “비교 정렬” 방식을 기반으로 했다.
하지만 지수 정렬은 숫자가 가지는 특성, 즉, 이진법에 의한 자릿수를 기반으로 정렬을 한다.

사실 이렇게만 설명하면 이해가 쉽지 않기 때문에 아래의 시각자료를 보며 이해하면 좋을 것 같다.

10진수 기준 각 자리수의 값(0~9)을 각각 하나의 상자들로 구성해준다고 생각한다. 그리고 가장 첫번째 자리수 부터 검사를 시작하는데, 첫 자리수가 0이면 0에 담고, 8이면 8에 담듯 숫자의 절대적 크기는 고려하지 않은채 각 자리수의 크기로만 배열을 골라낸다. 그렇게 가장 긴 자리수 까지 검사를 완료하면 숫자가 오름차순으로 올바르게 정렬되는 것을 확인할 수 있다.

이는 각 숫자들의 절대적 크기를 비교한 것이 아닌, 각 자리수를 비교하며 정렬을 한 것이기 때문에 이전의 정렬 방식과는 큰 차이점을 보인다고 할 수 있다.

---

getDigit 헬퍼 (step 1)

우리는 자리수 별로 숫자들을 비교해나가야 하기 때문에, 각 숫자들의 n자리수 값이 무엇인지 반환해주는 getDigit() 헬퍼 함수가 필요하다.

function getDigit(num, i) {
  // (num의 절대값을 10의 i제곱으로 나눈 값) % 10 => 내림처리
  // 만약 i가 2라면, 100의자리수를 구하는 것이기 때문에 10의 2제곱인 100으로 num을 나누게 된다
  // 그리고 그 값은 자리수가 얼마나 크건간에 나눗셈에 의해 1의 자리수가 된다.
  // 이를 10으로 나눈 나머지는 1의자리수만 남게 되기 때문에 해당 자리수를 쉽게 구할 수 있다.
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

---

digitCount 헬퍼 (step 2)

이제 자리수들을 도출하는 헬퍼 함수를 구현했으니, 반복문을 돌리기 위해 각 숫자들의 총 자리수가 몇인지 반환해주는 digitCount() 헬퍼함수를 구현해야 한다.

function digitCount(num, i) {
  // 0log10의 값은 -Infinity가 나오기 때문에 0의 경우에는 아래와 같이 처리해줘야 한다.
  if (num === 0) return 1;
  // 10의 몇 제곱을 해야 num이 나오는지 반환해준다. 1234의 경우 10의 3제곱이 1000이다.
  // 따라서 3 + 1을 해주면 1000의 자리에 해당하는 4가 올바르게 반환될 수 있다.
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

---

maxDigit 헬퍼 (step 3)

위에서 각 숫자들의 총 자리수 길이를 구하는 헬퍼함수를 구현했다.
따라서 이제 해당 숫자들 중에서 가장 긴 자리수를 반환해주는 maxDigit() 헬퍼 함수만 구현해주면 된다.

function maxDigit(arr) {
  let maxDigits = 0;
  for (let i = 0; i < arr.length; i++) {
    // 여기서 위에서 구현해둔 digitCount 헬퍼함수를 호출해서 사용하면 된다.
    maxDigits = Math.max(maxDigits, digitCount(arr[i]));
  }
  return maxDigits;
}

---

지수 정렬 구현 (step 4)

이제 위의 모든 헬퍼 함수들을 활용해서 지수 정렬을 구현해주기만 하면 된다.

Array.from()

전혀 활용하고 있지 못했던 메소드다…. 신세계였어서 한번 정리를 해봤다.

let testArray = Array.from({ length: 10 }, () => []);
// 이렇게 하면 testArray는 10의 길이를 갖고, 각 요소들이 빈 배열 []로 채워지는 배열이 된다.

지수 정렬 구현

function radixSort(arr) {
  // 최대 자리수 카운트 반환
  let maxDigits = maxDigit(arr);
  // 최대 자리수를 기준으로 첫 번째 반복문 구성
  for (let i = 0; i < maxDigits; i++) {
    // 체크하는 자리수가 바뀔 때마다 bucket 초기화
    let bucket = Array.from({ length: 10 }, () => []);
    for (let j = 0; j < arr.length; j++) {
      let digit = getDigit(arr[j], i);
      // n번째 자리수가 m인 숫자들을 bucket[n]에 각각 담아줌
      bucket[digit].push(arr[j]);
    }
    // 그리고 그 자리수별 숫자들을 풀어서 arr의 값을 해당 값들로 바꿔줌
    arr = [].concat(...bucket);
  }
  return arr;
}

radixSort([8, 10, 345, 25, 777, 1928, 1994]);

---

지수 정렬의 시간복잡도

지수 정렬에 대한 시간복잡도는 두 쟁점이 존재한다.
하나는 지수정렬이 O(nk)라는 주장과, O(nlogn)이라는 주장이다.

아래 위키피디아에 들어가면 이에 대한 내용이 잘 정리되어 있다.

위키피디아_기수정렬

---