radixSort - 기수 정렬

 

 

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 이 문제는 기수 정렬을 이용해서 풀어야합니다. 그러나 기수 정렬은 계수정렬을 사용하기 때문에 계수정렬에 대해 먼저 공부한 다음에 기수정렬 알고리즘을 완료하면 됩니다.

계수정렬 참고:
링크1 

링크2

 

입력

인자 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]의 범위가 정수 전체로 확대될 경우, 기수 정렬 알고리즘을 완성해 보세요.

 

문제 풀이

// arr[i]는 0 이상의 정수
// arr.length 100,000 이하


//최대값 리턴 
function getMax(arr) {
    return arr.reduce((max, item) => {
      if (item > max) return item;
      return max;
    }, 0);
  }
  
//계수정렬
function countingSort(arr, radix) {
    //배열의 길이만큼 N을 할당 
    const N = arr.length;

    //다음 Array 함수로 배열을 설정 
    //배열의 길이만큼 output 설정 
    const output = Array(N).fill(0);
    
    //10개의 0을 원소로 갖는 배열 생성 
    const count = Array(10).fill(0);
    console.log("output",output, "count",count)
  
    // 현재 자리수를 기준으로 0~9의 개수를 센다.
    arr.forEach((item) => {
      const idx = Math.floor(item / radix) % 10;
      count[idx]++;
    });
    console.log("count",count)
  
    // 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--;
    }
    console.log("final", output)
    return output;
  }
  
  // naive solution
  // 양의 정수만 정렬 가능
  function radixSort2(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);
  }
  
let output = radixSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]