[알고리즘] 계수정렬

계수정렬(Counting Sort)

• 요소들을 비교하지 않고 빈도수를 체크하여 정렬하는 알고리즘
• 등장하는 요소의 범위가 작을 때 사용하면 좋다

ex) 710526460153625
빈 배열 = [0,0,0,0,0,0,0,0]

배열	요소
[0,0,0,0,0,0,0,1]	710526460153625
[0,1,0,0,0,0,0,1]	10526460153625
[1,1,0,0,0,0,0,1]	0526460153625
[1,1,0,0,0,1,0,1]	526460153625
[1,1,1,0,0,1,0,1]	26460153625
[1,1,1,0,0,1,1,1]	6460153625
[1,1,1,0,1,1,1,1]	460153625
[1,1,1,0,1,1,2,1]	60153625
[2,1,1,0,1,1,2,1]	0153625
[2,2,1,0,1,1,2,1]	153625
[2,2,1,0,1,2,2,1]	53625
[2,2,1,1,1,2,2,1]	3625
[2,2,1,1,1,2,3,1]	625
[2,2,2,1,1,2,3,1]	25
[2,2,2,1,1,3,3,1]	5
print	001122345556667

특징

• (요소의 최댓값 + 1)만큼의 배열이 필요하므로 메모리의 낭비가 있을 수 있다

시간복잡도

• 일반적으로 $O(n)$
• 요소의 범위에 영향을 받으므로 최악의 경우 $O(n+k)$ ($k$ : 요소의 최대 범위)