코플릿_[radixSort]

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

입출력 예시

let output = radixSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

풀이

// 최대값 
function getMax(arr) {
  return arr.reduce((max, item) => {
    if (item > max) return item;
    return max;
  }, 0);
}

// radix = 기수(基數), 자릿수(1, 10, 100)
function countingSort(arr, radix) {
  const N = arr.length;
  const output = Array(N).fill(0); 
  const count = Array(10).fill(0);
  // output -> [0,0,0]
  // count -> [0,0,0,0,0,0,0,0,0,0]

  arr.forEach((item) => {
    const idx = Math.floor(item / radix) % 10;
    count[idx]++;
  });
  // count -> [0,2,0,1,0,0,0,0,0,0]
  // 현재 자리수를 기준으로 0~9의 개수를 센다

  count.reduce((totalNum, num, idx) => {
    count[idx] = totalNum + num;
    return totalNum + num;
  });
  // count -> [0,2,2,3,3,3,3,3,3,3]
  // 누적 개수가 되도록 만든다.

  let i = N - 1;
  while (i >= 0) {
    const idx = Math.floor(arr[i] / radix) % 10;
    output[count[idx] - 1] = arr[i];
    count[idx] -= 1;
    i--;
  }
  return output;
}

function radixSort(arr) {
  let left = [];
  let right = [];
  arr.forEach((item) => {
    if (item >= 0) right.push(item);
    else left.push(item * -1);
  });

  let max = getMax(left);
  let radix = 1;
  while (parseInt(max / radix) > 0) {
    left = countingSort(left, radix);
    radix *= 10;
  }

  max = getMax(right);
  radix = 1;
  while (parseInt(max / radix) > 0) {
    right = countingSort(right, radix);
    radix *= 10;
  }

  return left
    .reverse()
    .map((item) => item * -1)
    .concat(right);
}

작동 과정은 다음과 같다.

1. 양수(right), 음수(left) 구분
2. 음수(left) 양수로 변환
3. 각각 countingSort를 이용해 정렬
4. 음수(left) 음수로 변환 후 양수(right)와 concat

여기서 radix는 기수(基數), 즉 기준이 되는 수로 1, 10, 100 등의 자리수를 의미한다. max는 바로 이 radix 설정을 위한 장치이며, 만약 max가 9라면 10의 자리는 구할 필요가 없어진다.

그렇다면 Radix sort와 Counting sort의 차이점은 무엇일까? 만약 1의 자리와 10의 자리, 100의자리 등으로 나누지 않고 그 자체를 counting으로 정렬하려면 입력값 만큼의 배열이 필요할것이다. 이를 보완하여 자리수 별로 나누어 0 ~ 9 까지 정렬하는 것을 Radix sort라고 부른다.

참고
카운팅 정렬, 래딕스 정렬