JavaScript에서 카운팅 정렬 구현

숫자 배열을 받아 카운팅 정렬 알고리즘을 사용하여 정렬하는 JavaScript 함수를 작성해야 합니다.

최대값을 알면 계수 정렬 알고리즘을 사용하여 선형 시간 및 공간에서 숫자 배열을 정렬할 수 있습니다. 최대값을 사용하여 해당 크기의 배열을 만들어 각 인덱스 값의 발생 횟수를 계산합니다.

그런 다음 0이 아닌 개수가 있는 모든 인덱스를 결과 배열로 추출합니다.

우리는 먼저 하나의 루프를 사용하여 배열의 가장 큰 요소를 찾을 것이며, 일단 배열을 정렬하기 위해 카운팅 정렬을 사용할 것입니다.

예시

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 ]