계수 정렬(Counting Sort)

개념

계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다.

(계수 정렬은 비교 정렬이 아님)

 

 

예시

 

 

시간복잡도

시간 복잡도 : O(n + k) -> k는 배열에서 등장하는 최대값

 

 

 

 

 

 

 

 

 

 

---

 

참고 

https://gyoogle.dev/blog/algorithm/Counting%20Sort.html

https://ko.wikipedia.org/wiki/%EA%B3%84%EC%88%98_%EC%A0%95%EB%A0%AC