계수 정렬(Counting Sort)

배열 내 원소의 개수를 세어 위치를 결정하는 정렬 알고리즘

⇒ 각 원소가 몇 번 등장했는지를 카운팅한 후, 이를 이용해 정렬된 배열을 생성

• 비교 기반 정렬이 아니라 숫자의 크기 범위(최댓값)에 기반한 정렬
• 원소의 크기가 한정적이고 정수로 표현될 때 효율적인 알고리즘
• 힙 정렬(Heap Sort)이나 퀵 정렬(Quick Sort)과는 다르게 비교 연산이 없음
• 장점
  • 시간 복잡도가 O(n + k)로 매우 빠름 (k는 최댓값)
  • 비교 연산 없이 정렬 가능
  • 음수가 없고 데이터 크기가 제한적일 경우 매우 효율적
• 단점
  • 최대값을 기준으로 추가적인 메모리 공간이 필요 (O(k) 크기의 배열)
  • 데이터가 너무 크면 메모리 낭비가 심함
  • 정수 데이터가 아닐 경우 적용하기 어려움

진행 과정(오름차순 기준)

1. 입력 배열의 최댓값을 찾음
2. 최댓값을 크기로 갖는 카운트 배열을 생성하고, 모든 값을 0으로 초기화
3. 입력 배열을 순회하며 해당 값에 해당하는 카운트 배열의 인덱스를 증가
4. 카운트 배열을 누적합 형태로 변환하여 각 원소가 정렬된 위치를 찾음
5. 입력 배열을 역순으로 순회하면서 정렬된 배열을 생성

구현 코드(오름차순 기준)

const countingSort = (arr) => {
  const max = Math.max(...arr);
  const count = Array(max + 1).fill(0);
  const result = Array(arr.length);

  // 1. 카운트 배열 채우기
  arr.forEach(num => count[num]++);

  // 2. 누적합 변환
  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // 3. 입력 배열을 역순으로 순회하면서 결과 배열 채우기
  for (let i = arr.length - 1; i >= 0; i--) {
    result[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }

  return result;
};

const testArr = [4, 2, 9, 1, 5, 6, 4, 2];
console.log(countingSort(testArr)); // [1, 2, 2, 4, 4, 5, 6, 9]

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 최선: O(n + k)
  • 평균: O(n + k)
  • 최악: O(n + k)
• 공간 복잡도
  • O(n + k) (카운트 배열과 결과 배열이 필요)