【アルゴリズム(JS実装)】Counting Sort

　どうも、わくばです！

　先日。E資格に申し込んだと言ったのですが、試験会場が都心しか空いていないことと、その他大学の実習の都合などいろいろ加味した結果、キャンセルして見送ることにしました。

　JDLA認定は二年間有効なので、また機を見て受験しようと思います。

　一応報告でした。

　さて今日勉強したのは、Counting Sortです。まず出現回数をカウントし、その情報を回数と値がペアになるように別の配列に保持しておきます。今回は出現回数をvalue、何の値かをindexとして配列を作成しています。値をindexとすることで自然にソートされます。

　以下がコードです。 

const countingSort = array => {
  if (array.length < 2) { 
    return array;
  }
  
  //数え上げるための配列
  const counts = [];

　/**
  まず配列の最大値の数だけメモリを確保する
  ここからはcounts配列のインデックスが出力時の
  valueに相当する
  **/
  for(let i=0; i<=Math.max(...array); i++){
      counts.push(0);
  }
　
　/**
  出現した回数をカウント
  6が二回出現したとするとcounts配列の
  6番目に2が入る
  **/
  array.forEach(x => {
    counts[x]++; 
  });

  /**
  accumulationをresnlt,
  currentをcount,
  indexをidxとしている。
  countがなくなるでpushする。
  例えばcounts配列の6番目に2が入っていたら
  6を2回pushする  
  **/
　return resultArray = 
    counts.reduce((result, count, idx) => {
        while (count > 0) { 
            result.push(idx); 
            count--; 
        }
        return result;
    },[]);
}

let array = [22,3,5,4,27,8,9,5,4,33,7,8,9,4,2,22]
console.log(countingSort(array);

>>>[
    2, 3, 4, 4, 4, 5,
    5, 7, 8, 8, 9, 9,
    22, 22, 27, 33
   ]

　今回はreduceを使ってみました。ちょっとスッキリするかと思います。

　Complexity

　入ってきた配列の長さをn、配列の中の最大値をkとすると、まずcounts配列が完成しきるまでで\(O(n+k)\)になります。

　そのあとcountsにreduceをかけるので\(O(k)\)、中のwhileはnの長さの配列を作るためreduceの一回一回を跨いで合計すると\(O(n)\)必要になります。単純に合わせて\(O(nk)\)と考えてしまいたくなりますが、このときのnとkは依存せず、かつk回の処理のうち何もしない時もあるので、nとkは掛け算ではなく足し算で考えるほうが正確です。全部見に行く処理でk回かかり、countのvalueに応じてwhileが実行されます。つまり、結果としてreduceの部分は\(O(n+k)\)と捉えられます。

　以上から\(O(2(n+k))\)で、係数を無視して\(O(n+k)\)と言えます。