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

알고리즘

황칠이 2021. 1. 19. 15:15

계수정렬(카운팅 알고리즘) Counting Sort

수의 범위가 작을 때 더욱 빠르게 정렬할 수 있는 알고리즘

복잡도 O(n+k) k:가장 큰 수

k가 n보다 작은 경우 O(n)으로 빠르게 정렬할 수 있지만

k가 n보다 매우 큰 경우 O(n), O(n으로 비효율적이다.

-> 정렬한 수들의 최대값에 영향을 많이 받는다.

비교 정렬이 아니며

같은 숫자 정렬이라도 순서가 섞이지 않는 안정 정렬이다.

* 참고 - 애니메이션

출처