[자료구조] Counting Sort (계수 정렬)

개념

배열내의 수의 개수를 저장해서 작은 수부터 개수만큼 값을 입력해서 정렬하는 방식

비교연산이 없음
배열내 최대 값 +1만 길이의 배열이 필요
max값 산출이 선행되어야 함
정수만 정렬 가능
누적합을 생성하여 누적합을 기준으로 정렬할 경우 안정정렬이 보장됨

과정

1. 카운팅 배열 생성

https://soobarkbar.tistory.com/101?category=848286

2. 카운팅 배열로 누적합 생성

https://soobarkbar.tistory.com/101?category=848286

3. 입력 배열과 동일한 크기의 출력 배열을 생성, 입력 배열의 역순으로 출력 배열에 요소들을 채움

https://soobarkbar.tistory.com/101?category=848286

시간 복잡도

(Best = Average = Worst) = O(N)