정렬 4(계수정렬)

출처 : (이코테 2021 강의 몰아보기) 4. 정렬 알고리즘
https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

계수정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용가능
데이터의 개수가 N, 데이터(양수)중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장
계수정렬은 때에 따라서 심각한 비효율성을 초래할 수도 있음 EX) 데이터가 0과 999,999 단 2개만 존재하는 경우 => 데이터가 2개뿐이지만 배열은 백만개를 만들어야하므로 공간적으로 매우 비효율적
계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있음 EX) 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적

코드

#계수 정렬
array=[7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count=[0]*(max(array)+1)
for i in range(len(array)):
    count[array[i]]+=1

for i in range(len(count)):
    for _ in range(count[i]):
        print(i,end=' ')