계수 정렬( Count Sort )

계수 정렬

• 숫자들간 비교를 하지 않고 정렬을 하는 알고리즘
• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.
  • 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용
• 계수 정렬은 최악의 경우에도 수행시간 O(N + K)를 보장
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다

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

이런 형태의 배열이 있다고 가정 한다면

# 모든 범위를 포함하는 리스트를 선언 후 모든 값을 0으로 초기화
count = [0] *(max(array) + 1)

for i in range(len(array)):
	count[array[i]] += 1	# 각 데이터에 해당하는 인게스의 값을 1씩 증가

💡 array의 원소에 한개씩 접근해 가면서 해당 값에 대한 count 리스트에 +1을 해준다.

# count 리스트에 저장되어 있는 정보 확인
for i in range(len(count)):
	for j in range(count[j]):
    	print(i, end=' ')

~~> 
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

계수 정렬의 시간 복잡도

• 데이터의 개수 : N
• 데이터 중 최대값의 크기 : K
• $O(N + K)$

  앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라 추후에 리스트의 해당하는 값을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문에