Py) 계수정렬 Counting Sort

• 특정 조건일 때만 사용 가능하며 매우 빠름
• 데이터 크기 범위가 제한 되어 있을 경우와 정수 형태로 표현 할 수 있을 때 사용
• 안정정렬
• 복잡도 분석:
  • 데이터 개수 N, 최대값(양수) K이다. 최악의 경우(데이터의 범위가 너무 큰 경우 ex. 0 ~ 99999)에도 O(N+K) 유지

 

알고리즘

1. 입력받는 데이터의 범위를 포함할 수 있는 리스트를 생성한다.
2. 생성한 리스트에서 각 데이터에 해당하는 인덱스의 값을 증가시킨다.

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 j in range(count[i]): #출력
        print(i, end = ' ')