TIL. Radix Sort

Sort의 종류는 참 다양하다...

Bubble, Quik, Insert, Merge 등... 세상에는 sort의 종류가 참 많다.

Radix sort는 무엇인가?

근데 먼저 Counting sort를 공부해야 했다...

5, 1, 3, 4, 1, 2, 5, 6 이라는 A 수열을 정렬한다고 하자

1. 우선 최대 숫자 6을 참조하여 index 6까지 존재하는 '0'으로 이뤄진 B 배열을 만들어 보자
   B = [0, 0, 0, 0, 0, 0, 0]
2. A 수열의 각 수가 몇 번 등장하는지를 B 배열에 카운트해보자
   B = [0, 2, 1, 1, 1, 2, 1]
3. B 배열의 누적합으로 변경해준다.
   B = [0, 2 (0+2), 3 (2+1), 4 (3+1), 5 (4+1), 7 (5+2), 8 (7+1)]
   => 1번 index (A 배열에서 숫자 1)의 2라는 누적합을 통해 A 배열의 숫자 1들이 정렬될 배열에 1, 2번째에 들어가야 한다는 걸 알게 되었다.
4. 결과로 나와야 할 N (A 배열의 총 수)개의 '0'으로 이뤄진 배열을 만든다.
   output = [0, 0, 0, 0, 0, 0, 0, 0]
5. B 배열에서 가장 뒤에 있는 누적합을 통해 6의 위치를 조정해 보자. B 배열에 누적합이 8이라고 하면 6은 output의 8번째 자리 (7 index)에 위치해야 한다.
   output = [0, 0, 0, 0, 0, 0, 0, 6]
   그리고 다음에 또 6이 있는 경우도 있을 수 있으니 누적합 8을 7로 변경해 준다.
   B = [0, 2, 3, 4, 5, 7, 7]
6. 위와 같이 수의 누적합을 이용하여 index 위치를 찾아주는 sort 방법이 Counting sort이다.

본격 Radix sort를 공부해보자

Radix Sort (기수 정렬)는 배열 요소의 각 자리수를 확인하여 미리 준비한 일명 자리수 배열에 위치하도록 하는 것이다. 해당 sort는 다른 수들과 비교를 통해 정렬을 하지 않는다.

1, 11, 20, 21, 35, 101, 50 를 정렬한다고 해보자

1) 1의 자리수로 0~9 인덱스에 위치하도록 먼저 정렬한다.

[20, 50, 1, 11, 21, 101, 35]로 정렬되었다.

2) 10의 자리수로 다시 0~9 인덱스에 위치하도록 정렬한다. (10이하의 수의 10의 자리수는 0으로 한다)

[1, 101, 11, 20, 21, 35, 50]로 정렬되었다.

3) 마지막 100의 자리수로 다시 0~9 인덱스에 위치하도록 정렬한다.

4) [1, 11, 20, 21, 21, 35, 50, 101]로 모든 정렬을 마친다.

Radix sort를 구현하려고 보니, Counting sort와 닮아 있는 부분이 많았다. 미리 0~9의 배열을 만들어 놓고 각 정렬하고자 하는 수를 그 배열의 인덱스로 매칭하여 정리하는 것이 공통점이었다.

구현

// 배열에서 가장 큰 수를 먼저 구한다. Radix의 범위를 정하기 위함이다.
function getMax(arr) {
  return arr.reduce((max, item) => {
    if (item > max) return item;
    return max;
  }, 0);
}

// 먼저 counting sort의 식을 구해보자
function countingSort(arr, radix) {
  const N = arr.length;
  
  // 재정렬하기 위한 준비 배열
  const output = Array(N).fill(0);
  
  // 0부터 9까지의 준비 배열 (각 자리수의 수의 누적합 계산을 위한 배열)
  const count = Array(10).fill(0);

  // 현재 자리수(radix: 1, 10, 100...)를 기준으로 배열의 0~9의 개수를 센다. 나중에 Radix sort에서 radix별로 계속 loop해 줄 예정이다.
  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;
}

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);
  
  // 1의 자리부터 시작...
  let radix = 1;
  
  // 최대 수의 자리수까지만 while...
  while (parseInt(max / radix) > 0) {
    // 정렬의 결과를 다시 left 배열로 할당한 후 radix 자리수를 10씩 곱해준다.
    left = countingSort(left, radix);
    radix *= 10;
  }

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

  return left
  // 양수로 정렬되었던 left 배열을 reverse 후  -1를 곱해준 배열에 right 배열을 concat 해준다
    .reverse()
    .map((item) => item * -1)
    .concat(right);
}