[알고리즘/javascript]radixSort

문제

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

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 0 이상의 정수
• arr.length 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 기수 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

힌트

• 기수 정렬(radix sort)은 내부적으로 계수 정렬(counting sort)을 사용합니다.
• 계수 정렬을 먼저 학습하고, 어떤 경우에 기수 정렬을 사용하는지 학습하도록 합니다.

Advanced

• arr[i]의 범위가 정수 전체로 확대될 경우, 기수 정렬 알고리즘을 완성해 보세요.

---

계수정렬

각 요소의 배열 등장 횟수를 count해 누적합으로 나타내는 배열을 만든 뒤, 그 누적합으로 요소들의 index를 알아내 작은 숫자 순서대로 정렬하는 기법

function countingSort(arr) {
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  let count = {}; // 누적합 나타내는 객체 사용
  
  for (let i = min; i <= max; i += 1) {
    count[i] = 0; // min부터 max까지 0으로 채운 객체 준비
  }
  for (let i = 0; i < arr.length; i += 1) {
    count[arr[i]] += 1; // arr를 순회하며 요소 개수 적립
  }
  
  let sortedArr = [];
  for (let i = min; i < max; i += 1) {
    while (count[i] > 0) { // count값이 0이 될때까지 정렬배열에 요소 삽입
      sortedArr.push(i); // 요소 삽입 후 
      count[i] --; // count값 -- 처리
    }
  }
  
  return sortedArr;
};

 

기수정렬

0의 자리, 10의 자리, 100의 자리 ... 1 * (0의 n개) 자리수를 기준으로 정렬하는, 비교 연산을 하지 않는 정렬 기법

내부적으로 계수정렬 사용 

// 양의 정수만 정렬 가능한 로직
function radixSort(arr) {
  const max = Math.max(...arr);
  let radix = 1; // 자릿값
  while (parseInt(max / radix) > 0) { // 최댓값이 가지는 자릿수까지만 반복
    arr = countingSort(arr, radix); // radix를 지정해서 인자로 받는 countingSort 함수를 내부적으로 이용
    raidx *= 10;
  }
  return arr;
};

 

이해에 참고하기 좋은 블로그

https://gaemi606.tistory.com/entry/%EA%B8%B0%EC%88%98-%EC%A0%95%EB%A0%ACRadix-sort

기수 정렬(Radix sort) / 계수 정렬(Counting sort)

https://velog.io/@wjdqls9362/Algorithm-%EC%A0%95%EB%A0%AC-Radix-sort-Counting-sort

[Algorithm] 정렬 : Counting sort(계수 정렬), Radix sort(기수 정렬)

---

코드

양의 정수만 정렬

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 
  );

  // 아래 속성이 유지되도록 하기 위해 배열을 거꾸로 순회한다.
  //  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]--;
    i--;
  }

  return output;
}

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

 

음수까지 정렬 가능

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 
  );

  // 아래 속성이 유지되도록 하기 위해 배열을 거꾸로 순회한다.
  //  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]--;
    i--;
  }

  return output;
}

// naive solution
//양의 정수만 정렬 가능
// function radixSort(arr) {
//   const max = Math.max(...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 = Math.max(...left);
  let radix = 1;
  while (parseInt(max / radix) > 0) {
    left = countingSort(left, radix);
    radix *= 10;
  }

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

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