TIL. Radix Sort

Sortの種類は本当に多いです...

Bubble Quik Insert Mergeなど...世界にはsortの種類が多いですね.

Radix sortとは?

でもまずCounting sortを勉強しなければなりません...

5,1,3,4,1,2,5,6というA数列を列挙します.

まず最大数6を参照してindex 6までの「0」のB配列を作成するB = [0, 0, 0, 0, 0, 0, 0]

A数列の各数列に何回現れるB数列を計算します.B = [0, 2, 1, 1, 1, 2, 1]

B配列の積算和に変更します.B = [0, 2 (0+2), 3 (2+1), 4 (3+1), 5 (4+1), 7 (5+2), 8 (7+1)]=>1番インデックス(A配列中の数字1)の2の累積により,A配列中の数字1はソートする配列の1,2番目に位置しなければならないことが分かった.

の結果から、N(A配列の総数)個の「0」の配列が作成される.output = [0, 0, 0, 0, 0, 0, 0, 0]

B配列では、最後尾の累加により6の位置が調整される.B配列積算が8の場合、6は出力の8番目のビット(7 index)にある必要があります.output = [0, 0, 0, 0, 0, 0, 0, 6]また、次が6で、累計8が7になる可能性もあります.B = [0, 2, 3, 4, 5, 7, 7]

ビットに示すように、数の累積を用いてインデックス位置を検索するsort法はcounting sortである.

正式にRadix sortを勉強します

Radix Sort(基数ソート)は、アレイ要素の各ビット数を決定し、予め準備されたビット数と呼ばれるアレイに配置するものである.このsortは他の数と比較してソートされません.
1、11、20、21、35、101、50を並べ替えてみましょう.
1)0から9のインデックスに1のビット数で最初に配置します.
[20, 50, 1, 11, 21, 101, 35]に並びます.
2)0～9のインデックスに10の桁数で並べ替えます.(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);
}