🚩 카운팅 정렬 (Counting Sort)

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하는 알고리즘
• $O(n+k)$ : n - 리스트 길이 / k - 정수의 최대값
• 제한 사항
  • 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능하다.
  • 공간복잡도가 큰 단점이 있다.

1. 각 항목의 발생 횟수를 기록하기 위한 카운팅 배열 만들기
2. 카운팅 배열을 앞에서부터 누적합한다.
3. 원본 데이터 배열을 뒤에서 부터 탐색하며 누적합의 위치에 요소를 둔다.
   • 단, 중복된 정수가 있을 경우 -1한 값에 위치시킨다.

⭐ 뒤에서부터 처리하는 이유
stable 유지 : 동일 값이면 순서를 유지하기 위함이다.

구현 방법