[자료구조 및 알고리즘] 계수정렬(Counting Sort)

계수정렬

 

특정 조건이 부합할 때만 사용할 수 있는 정렬이지만, 매우 빠른 정렬 알고리즘이다.

 

조건

 

1. 최소값과 최대값의 차이가 100만 이하일 경우

2. 데이터가 양의 정수일 경우

3. (+데이터 크기가 많이 중복되어 있을 경우)

 

특징

 

가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 사용할 수 없다. 모든 범위르 ㄹ담을 수 있는 크기의 리스트를 선언해야하기 때문이다.

 

계수정렬은 직접 데이터의 값을 비교한 후에 위치를 정렬하는 방식이 아니다. 별도의 리스트 선언 후, 그 안에 정렬에 대한 정보를 담는다.

 

데이터 범위가 한정되어 있으면 효과적으로 사용할 수 있다. 항상 빠르게 동작하며, 기수정렬과 더불어 가장 빠른 정렬 알고리즘이다.

 

코드

 

# 계수정렬

array_1 = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
counting_list = [0] * (max(array_1)+1)

for i in range(len(array_1)):
	counting_list[array_1[i]] += 1

for i in range(len(counting_list)):
	for j in range(counting_list[i]):
    	print(i, end=' ') # 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

시간복잡도

O(N+K)

 

앞에서부터 데이터를 하나씩 확인한 후 리스트 인덱스 값 1씩 증가 + 인덱스에 해당하는 값들을 확인할 때 최대값의 크기만큼 반복수행