계수 정렬 (Counting Sort) 설명과 JavaScript 예제

계수 정렬(Counting Sort)은 비교 기반이 아닌 값의 개수를 세는 방식으로 정렬하는 특수한 알고리즘입니다. 숫자의 범위가 제한적이고 정수가 많은 경우 매우 빠른 성능을 발휘합니다. 다만, 일반적인 정렬 알고리즘과 달리 객체 정렬이나 실수 정렬에는 적합하지 않습니다.

---

1. 동작 원리

1. 입력 배열에서 최대값을 찾는다
2. 0부터 최대값까지를 인덱스로 하는 카운트 배열(count array)을 생성
3. 입력 배열의 각 요소가 몇 번 나왔는지 카운트
4. 카운트 배열을 누적합 형태로 변환 (위치 정보로 사용)
5. 원래 배열을 뒤에서부터 순회하며, 결과 배열에 값을 채움

→ 정렬된 결과가 새로운 배열로 만들어지는 방식입니다.

---

2. JavaScript 예제 - 오름차순 정렬

function countingSort(arr) {
  if (arr.length === 0) return arr;

  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);

  // 카운팅
  for (let num of arr) {
    count[num]++;
  }

  // 누적합으로 변경
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // 결과 배열 생성
  const result = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const num = arr[i];
    result[--count[num]] = num;
  }

  return result;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]

• 입력 값은 양의 정수여야 하며, 범위가 너무 크면 비효율적
• 결과 배열은 원본 배열과 길이가 같고 정렬된 값으로 채워짐

---

3. 성능 분석

구분	시간 복잡도
최선의 경우	O(n + k)
평균	O(n + k)
최악의 경우	O(n + k)

• n: 입력 배열의 크기
• k: 최대값 (값의 범위)
• 공간 복잡도: O(n + k)
• 안정 정렬: 같은 값의 순서가 유지됨

---

4. 계수 정렬의 특징

• 음수나 실수, 객체는 처리 불가 (정수만 가능)
• 값의 범위가 작고 중복이 많은 데이터에 적합
• 정렬 속도는 매우 빠르지만, 메모리 사용이 많을 수 있음

---

마무리

계수 정렬은 데이터의 특성이 잘 맞을 경우 매우 빠르고 효율적인 정렬 알고리즘입니다. 하지만 범용 정렬로 사용하기에는 제약이 많기 때문에 특정한 상황(정수 + 제한된 범위)에서만 적용하는 것이 좋습니다.

실제 사용보다는 알고리즘 학습 또는 제한적인 환경에서 선택적으로 사용하는 방식입니다.