[정렬] 계수 정렬(Count Sort)

- 별도의 모든 범위를 담을 수 있는 리스트 선언 후, 한번에 반환받는 방식(비교 기반이 아님)
- 특정 조건 부합시에만 사용 가능(데이터가 정수 형태 / 데이터의 범위 ≤ 1,000,000)

 

시간 복잡도 : O(N + K) 
공간 복잡도: O(N + K) 범위의 끝과 끝 두값이 있는 경우, 비효율적

N: 데이터의 개수, K: 데이터의 최대값

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1) #0 ~ 9 면 10개임

for i in range(len(array)):
    count[array[i]] += 1
    
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end= ' ')

 

 

---

정렬 전체가긔

이것이 코딩 테스트다 - 나동빈
정리하긔