TIL. 46カウントソート

カウントソート(Counting Sort,カウントソート)は、配列内の要素を比較ソートするのではなく、これらの要素をカウントソートするアルゴリズムです.

質問する

要素範囲0 <= arr[i] < 100の配列のカウントソート

function countingSort(arr) {

  // 빈도가 담길 새 배열 선언
  // counting을 위해 0으로 세팅
  
  let counts = Array(100).fill(0);
  
  // arr의 각 요소를 돌면서 요소에 대해 counting한다.
  // 카운트는 새 배열에서 진행된다.
  // ex: 요소가 63일 경우, counts 배열의 63번째를 카운트 진행
  
  arr.forEach((num) => ++counts[num]);
  
  return counts;
}

カウントソートは、各要素の周りで行われ、これらの要素をカウントし続けて数値を増やします.

限られたデータの中で最も速いソートアルゴリズムです.