[알고리즘] 계수 정렬

✅ 계수 정렬 (Counting Sort)

❕ 기본 개념 

- 말 그대로 각 요소의 갯수를 세어서 저장해두고, 그에 따라 적절한 위치에 정렬하는 알고리즘

- 값의 범위가 너무 크면 안 되고, 각 항목의 갯수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있다는 한계가 존재함

- 비교 정렬 알고리즘의 최소 시간복잡도가 O(n logn)인데에 비해 계수 정렬은 평균 O(n)의 시간복잡도를 가짐

- 다만 공간복잡도가 O(size)이기 때문에 메모리 낭비가 심함

 

❕ 작동 방식 

 

outline

 

List -> Count -> Sorted List

 

 

✔ 구현 방법 (JS) 

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

// output
// [ 1, 2, 3, 3, 4 ]

 

 

참고자료

https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

https://velog.io/@chappi/알고리즘-6일차-On-정렬-계수-정렬

https://wondytyahng.tistory.com/entry/카운팅정렬

https://www.tutorialspoint.com/implementing-counting-sort-in-javascript