Algorithm problem-24

1. 문제

• 정수를 요소로 갖는 배열을 오름차순 정렬하여 리턴
• 기수 정렬(radixSort), 내부적으로 계수 정렬을 사용함(counting sort)

2. 시도

• 문제를 먼저 이해하고 진행해야 한다고 함
• 기수 정렬을 하기 위해 우선 계수 정렬부터 이해를 해야 한다고 함
• 기수 정렬의 자리수 정렬(1의 자리, 10의 자리, 100의 자리..)에 사용
• 각 자리수를 계수 정렬하면서 진행하면, 마지막 자리수를 정렬하고 나면
• 정렬이 완성이 된다고 함...신기하다
• [123,243,353,452,651,782,823,455] 배열이 주어짐
• [651,452,782,123,243,353,823,455] 1의 자리 정렬
• [123,823,243,651,452,353,455,782] 10의 자리 정렬
• [123,243,353,452,455,651,782,823] 100의 자리 정렬
• 즉, 각 자리수를 미리 정렬해둔다고 보면 되는데
• 위의 배열에서는 같은 100의 자리를 가진 452,455가 정렬될 때에 1의 자리만 다르기 때문에
• 1의 자리를 기준으로 정렬이 되기만 하면 됨
• 각 자리수를 정렬하는 데에 기수 정렬을 이용하고

3. 수도코드

// 양수만 가능함, 계수 정렬은 레퍼런스의 코드를 참조할 것
function radixSort(arr) { 
  const max = Math.max(...arr.slice());
  let radix = 1; //1의 자리부터 시작, 10씩 곱하여 최대수의 자리수까지만 정렬
  // 최대수와 자리수를 나눈 값이 0보다 작아지면, 최대 자리수를 넘어가므로 정렬 종료
  while (parseInt(max / radix) > 0) { 
    arr = countingSort(arr, radix);
    radix *= 10; //10씩 곱하여 자리수를 올려준다
  }
  return arr;
}

4. 레퍼런스

// 계수 정렬을 해줄 함수를 먼저 구현한다
function countingSort(arr, radix) {
  const N = arr.length;
  const output = Array(N).fill(0);
  const count = Array(10).fill(0);
  arr.forEach(item => {
    const idx = Math.floor(item / radix) % 10;
    count[idx]++;
  });
  count.reduce((totalNum, num, idx) => {
    count[idx] = totalNum + num;
    return totalNum + num;
  });
  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 = Math.max(...left.slice());
  let radix = 1;
  while (parseInt(max / radix) > 0) {
    left = countingSort(left, radix);
    radix *= 10;
  }
  max = Math.max(...right.slice());
  radix = 1;
  while (parseInt(max / radix) > 0) {
    right = countingSort(right, radix);
    radix *= 10;
  }
  return left
    .reverse()
    .map((item) => item * -1)
    .concat(right);
}