그림으로 알아보는 카운팅 정렬 (counting sort)

카운팅 정렬 (=계수 정렬)

카운팅 정렬이란 중복허용 배열에서 각 요소의 개수를 바탕으로

정렬된 배열을 계산하는 방법을 의미한다.

정렬된 배열을 계산하기 때문에,

요소끼리 비교하는 과정이 없다.

시간 복잡도

카운팅 정렬은 도메인의 범위가 시간, 공간에 직접적인 영향을 준다.

도메인의 범위가 for의 순회횟수와 카운팅 배열의 크기에 연관되어 있기 때문이다.

배열의 크기가 n 이고, 도메인의 크기가 k이라고 하면.

여기서 카운팅 정렬의 시간 복잡도는 O(n+k)이다.

바꿔말하면, 도메인이 작을수록 그 효과는 극적이다.

O(n)에 가까운 비용으로 정렬할 수 있다!

음수를 포함하는 배열의 카운팅 정렬

카운팅 정렬을 이용하여 음수를 정렬해야 한다면, 

간단한 트릭을 사용하면 된다.

가장 작은 음수가 0이 되도록 

적당하게 W를 더하자.

예시는 아래 코드에서 살펴볼 것.

코드