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

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

 

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

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

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

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

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

 

비교 정렬이 아니며

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

 

 

 

* 참고 - 애니메이션 

http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

 

출처 

http:// https://bowbowbow.tistory.com/8

https://www.zerocho.com/category/Algorithm/post/58006da88475ed00152d6c4b