JavaScriptでのカウントソートの実装

数値の配列を受け取り、カウントソートアルゴリズムを使用してソートするJavaScript関数を作成する必要があります。

最大値がわかっている場合は、カウントソートアルゴリズムを使用して、線形時間と空間で数値の配列をソートできます。最大値を使用して、そのサイズの配列を作成し、各インデックス値の出現をカウントします。

次に、カウントがゼロ以外のすべてのインデックスを結果配列に抽出します。

最初に1つのループを使用して配列の最大要素を見つけ、それがわかったら、countingsortを使用して配列を並べ替えます。

例

const arr = [4, 3, 1, 2, 3];
const findMaximum = arr => arr.reduce((acc, val) => val > acc ? val: acc, Number.MIN_VALUE)
const countingSort = (arr = []) => {
   const max = findMaximum(arr);
   const counts = new Array(max + 1);
   counts.fill(0);
   arr.forEach(value => counts[value]++);
   const res = [];
   let resultIndex = 0;
   counts.forEach((count, index) => {
      for (let i = 0; i < count; i++) {
         res[resultIndex] = index;
         resultIndex++;
      };
   });
   return res;
};
console.log(countingSort(arr));

出力

そして、コンソールの出力は-

[ 1, 2, 3, 3, 4 ]