토이 24번(계수,기수정렬)

정렬편을 따로 만들어야 하나..
(고민좀...)

1)버블 정렬
2)삽입 정렬
3)퀵 정렬
4)힙 정렬
5)기수정렬
6)계수정렬
..
.

암튼 계수정렬 과 기수정렬르 정리해보겠습니다.

계수정렬

개념

원소들간의 비교를 하지 않고 정렬을 함.

시간복잡도는 O(N+K) => k가 n보다 작으면 O(N)이 되지만
크면...O(무한)이 될 수도 있다.

단, 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요하다는 점과, 가장 큰 숫자에 영향을 받는다는 점은 단점

그래도 적은 개수의 숫자를 정렬할 때는 계수 정렬을 사용하도록 !

기수정렬

개념

위 그림을 보면 쉽게 이해할 수 있다.
일의자리수를 확인해서 그 인덱스에 넣고
그 후에 다시 십의자리를 비교해서 인덱스에 넣는다.

(쉬운 예제라 딴지걸겠지만.. 이해가 쉽도록 만듬)

정렬이 싫다..........
(10cm를 싫어하는 이유가 있구나)

위 두개를 섞어보자~~ 오예

먼저 기수정렬를 생각해보자

function radixSort(arr) {
  const max = getMax(arr);
  let radix = 1;
  while (parseInt(max / radix) > 0) {
    arr = countingSort(arr, radix);
    radix *= 10;
  }
 return arr;
}

정답코드

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

function countingSort(arr, radix) {
  const N = arr.length;
  const output = Array(N).fill(0);
  const count = Array(10).fill(0);

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

  // count[i]가 i까지의 누적 개수가 되도록 만든다.
  count.reduce((totalNum, num, idx) => {
    count[idx] = totalNum + num;
    return totalNum + num;
  });

  // 아래 속성이 유지되도록 하기 위해 배열을 거꾸로 순회한다.
  //  1. 가장 큰 값을 먼저 본다.
  //  2. 가장 큰 값을 가장 마지막에 놓는다.
  let i = N - 1;
  while (i >= 0) {
    const idx = Math.floor(arr[i] / radix) % 10;
    // count[idx]: 현재 radix의 idx까지 누적 개수
    // count[idx]개만큼 있으므로, 인덱스는 count[idx] - 1
    output[count[idx] - 1] = arr[i];
    count[idx] -= 1;
    i--;
  }

  return output;
}

// naive solution
// 양의 정수만 정렬 가능
// function radixSort(arr) {
//   const max = getMax(arr);
//   let radix = 1;
//   while (parseInt(max / radix) > 0) {
//     arr = countingSort(arr, radix);
//     radix *= 10;
//   }
//   return arr;
// }

// 음의 정수를 포함한 기수 정렬
// 1. 주어진 배열을 음수 부분과 양수 부분으로 나눈다.
// 2. 음수는 절대값을 기준으로, 즉 양수로 변환하여 기수 정렬한다.
// 3. 양수를 정렬한다.
// 4. 정렬된 음수 부분을 다시 음수로 바꾸고 순서를 뒤짚는다.
// 5. 음수 부분과 양수 부분을 붙인다.
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);
}