Radix Sort

Radix Sort는 기수 정렬이라고 불립니다. 

기수를 이용해서 정렬을 진행하는 방식이라고 생각하시면 쉽게 이해할 수 있는 알고리즘입니다.

1. Radix Sort

기수 정렬은 지금까지 배운 다른 정렬과 달리 서로의 배열 대상과 비교를 하지 않습니다.

[3, 54, 7, 6103, 1045, 365, 356]

1의 자리 숫자를 0부터 9까지 숫자별로 나누어 놓습니다.

[3, 6103, 54, 1045, 365, 356, 7]

이후 배열을 위의 그림에서 정렬한 방식대로 새롭게 배열을 만들어줍니다. 그리고 다음에는 자연스럽게 10의 자리 숫자를 분류하게 됩니다.

 

이처럼 10의 자리 숫자가 정렬이 진행됩니다.

그러나 여기서 중요한 점은 3, 7과 같은 10의 자리가 없는 숫자는 어떻게 될까요?

바로 0이라는 숫자로 분류가 되어있습니다.

 

[3, 6103, 7, 1045, 54, 356, 365]

[3, 7, 1045, 54, 6103, 356, 365]

[3, 7, 54, 356, 365, 1045, 6103]

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

}