(Python)계수 정렬

계수 정렬은 단순하게 크기를 기준으로 세는 알고리즘. 범위 조건이 있는 경우에 한해서 굉장히 빠르다.

 

배열에 존재하는 수의 개수를 세어주고, 이 정보를 바탕으로 정렬을 수행한다.

그리고 여기서 수와 수의 개수는 배열 혹은 딕셔너리의 인덱스와 해당 값을 통해서 기록할 수 있다.

 

크기를 기준으로 갯수만 세면 되기 때문에  위치를 바꿀 필요가 없고 모든 데이터에 한 번씩만 접근하면 되기때문에 효율적이다.

 

빅오 > O(N)

 

array = [6,3,2,6,7,3] 			# 배열 생성

count = [0] * (max(array) + 1)	# 가장 큰 값 +1 의 크기를 가지는 count 배열 생성

for i in range(len(array)):		# 배열을 하나하나 읽음
    count[array[i]] += 1		# count 배열에 갯수 추가

for i in range(len(count)):		# 각각의 인덱스에서 몇번씩 등장했는지 확인
    for j in range(count[i]):	# 카운트 의 인덱스 값 출력
        print(i, end = "")

 

  계수 정렬은 정렬하고자 하는 배열의 최대값이 매우 클 때 메모리를 매우 비효율적으로 쓰게 된다는 단점이 있다.

만약 배열에 음수가 존재한다면 사용할 수 없다.