12-03-Counting-Sort¶
Counting Sort¶
수의 범위만큼 배열을 만들고 요소의 개수를 카운트하여 순서대로 정렬
- 수가 0에서 9999 사이라고 한다면 freq[10000] 배열을 선언해서 처리
- 만약 수의 범위가 0에서 999,999,999 까지라고 하면 크기가 10억인 배열이 필요
- 메모리 제한이 512MB라고 해도 int 기준 대략 1.2억인 배열밖에 잡을 수 없음
- 수의 범위가 어느 정도 한정적일 때에만 카운팅 소트 가능 -> 1000만 이하
시간복잡도
- 수의 범위=K개
- N개의 수를 freq 배열에 추가
- 총 K칸의 값을 확인하여 출력/정렬 수행
- O(N+K)