합병 정렬, 퀵 정렬, 힙 정렬은 빠른 정렬 알고리즘에 속하지만 이 보다 더 빠른 정렬 알고리즘이 있다고 해서 퀵 정렬과 힙 정렬을 기술하기 전에 먼저 가져와봤다. 계수 정렬(Counting Sort)의 시간 복잡도는 다음과 같다. 시간복잡도 O(n + k) O(n + k)일 때 상수 k는 무시해도 되지만 계수 정렬에서 k는 나름 시간 복잡도에서 중요한 요소가 될 수 있다. k는 정렬한 수 집합 중 가장 큰 값을 의미하는데 계수 정렬이 어떤 방식으로 이루어지는지 확인해보면 k가 왜 존재하는지 알 수 있다. 정렬 방법 계수 정렬은 합병 정렬이나 퀵 정렬과는 다르게 숫자를 비교하지 않고 모든 숫자의 개수를 세는 방식으로, 숫자를 센 다음 정렬하기 때문에 '계수 정렬'이라고 부르는 것이다. 계수 정렬은 정수일..
2. 계수 정렬(Counting Sort)