Counting Sort

• 참고 : BaaaaaaaarkingDog | [실전 알고리즘] 0x0F강 - 정렬 II

개념

• 값의 크기를 직접 세서 정렬하는 알고리즘
  • 비교 기반이 아닌 정렬
• 값이 정수 범위 내에 한정되어 있을 떄, 빠르게 동작
• 범위가 작고 양의 정수일 떄 사용

사용방식

• 가장 큰 정수 값을 찾음
• 찾은 정수 값 까지의 정수 배열을 생성
• 각 값이 몇 번 등장했는지 배열에 기록

주의 사항

• 메모리를 많이 먹기에 (가장 큰 값 만큼의 배열 크기), 값 범위가 작을 떄 사용

시간 복잡도

상황	시간
전체 데이터 스캔	O(N)
카운트 배열 작성	O(K)
누적합 계산	O(K)
결과 정렬 생성	O(N)