[알고리즘] 계수 정렬 (Counting Sort)

계수정렬의 개념

이전에 $O(n^2)$ 알고리즘은 자신의 옆에 수와 비교해야하므로 $n^2$의 한계를 벗어나지 못한다고 하였다. $O(nlogn)$ 알고리즘은 자신의 옆에 수 말고, 건너건너 수와 비교하여 하나 당 logn시간의 비교를 하여 $O(nlogn)$시간을 완성할 수 있었다. 그러나 이는 어떤 수와 비교를 하여 정렬을 한다면 결국 $O(nlogn)$시간을 벗어날 수 없다는 한계에 봉착한다는 것이다.

계수 정렬은 작은 숫자에서는 복잡도가 O(n+k)이다. k는 정렬할 수들 중에 가장 큰 값을 의미하는데 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다.
예를 들어 10개의 숫자를 정렬하는 데, 가장 큰 숫자가 100일 경우, 100(k)은 10(n)의 제곱이므로 O(n^2)이 된다. 1000이면 O(n^3)이 되죠.
즉 정렬할 수들의 최대값에 영향을 받는 알고리즘이라고 볼 수 있다.