Motivation

계수 정렬(Counting Sort)은 두 요소를 절대 비교하지 않습니다. 요소의 값을 count 배열의 인덱스로 직접 사용하여 선형 시간 안에 실행될 수 있게 합니다.

왜 계수 정렬을 배워야 할까요?

• 선형 시간: O(n + k)의 시간 복잡도로 실행되며, 여기서 n은 요소의 개수이고 k는 값의 범위입니다. k가 작을 때, 이는 O(n log n)보다 빠릅니다.
• 안정성 (주의 깊게 구현할 경우): 여러 번의 계수 정렬 과정을 연결하는 기수 정렬(Radix Sort)의 기초가 됩니다.
• 색다른 아이디어: 값을 비교하는 대신 빈도수를 세어 정렬합니다.

트레이드오프: count 배열을 위해 O(k)의 메모리가 필요하므로, 값의 범위가 매우 클 때(예를 들어, 10억까지의 숫자 몇 개를 정렬하는 경우)는 적합하지 않습니다.