TIL. 46 Counting Sort(계수 정렬)

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;
}

• 계수 정렬은 요소 하나하나를 돌며 해당 요소를 계속해서 카운트해 숫자를 늘려 나간다.

• 제한된 데이터에서는 가장 빠른 정렬 알고리즘이다.