13. 카운팅 정렬(A.K.A 계수 정렬)
알고리즘 공부
2019. 9. 29.
카운팅 정렬 시간 복잡도는 O(n+k) (k는 데이터의 최댓값을 의미한다.) 카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다. 쉽게 설명하자면 특정 데이터의 개수(1이 두 개 있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다. 이 경우에 데이터의 최댓값을 k라 두면, 시간 복잡도는 O(n+k). 하지만, 만약 k가 억 단위를 넘어간다면? n이 아무리 작아도 동작시간이 크다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다. 즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다. 카운팅..
