Counting Sort에 대해 설명해보세요.

---

Counting Sort의 작동 방식

계수 정렬은 배열 내에 특정 값의 개수에 따라 정렬을 수행하는 알고리즘이다. 각 값의 개수를 세기 위한 배열과 결과를 저장할 추가 배열이 필요하다. 그림을 통해 알아보자.

배열 A를 입력받고 개수를 저장하기 위한 배열 B와 결과를 저장할 C를 준비한다.

A를 순회하며 각 값들의 개수를 B의 인덱스에 맞게 저장한다(1이 2번 나왔으므로 B의 인덱스 1자리에 2를 넣어준다). 이때 B의 길이는 A의 최댓값보다 크게 결정되어야 한다.

A의 가장 뒤에서부터 값을 하나씩 꺼내어 B의 인덱스를 사용해서 C에 저장한다. 6이므로 B의 6번째 인덱스에서 값을 하나 감소시킨 후 C의 6번째 위치에 값을 저장한다. 이와 같은 방식으로 A의 첫 번째 숫자까지 C에 저장하면 정렬이 끝난다.

---

Counting Sort의 특징

• 시간 복잡도
  : 크기가 N인 배열에서 최댓값이 K일 경우 O(N+K)의 시간 복잡도를 가진다.

• 공간 복잡도
  : 최댓값인 K 크기의 갯수를 세기 위한 배열이 필요하므로 O(K)의 공간 복잡도를 가진다.

• 장점

  • 빠른 시간으로 정렬할 수 있다.

• 단점

  • 메모리 낭비가 심하다.
  • K 값이 클 경우 비효율적이다.

---

결론

Counting Sort는 데이터의 갯수에 따라 정렬하는 방식의 알고리즘입니다. 비교 연산 없이 진행되므로 O(N)의 빠른 시간 복잡도로 정렬이 가능하지만 개수를 저장할 추가 배열이 필요한데 이때 배열의 최댓값 크기 만큼의 배열이 필요합니다. 따라서 메모리 낭비가 심하므로 데이터의 크기가 한정적일 때 사용하는 것이 유리합니다.