[06정렬] 6-6 계수 정렬 (p171 ~ p174)

[계수 정렬]

• 특정한 조건이 부합할 때만 사용할 수 있음. 매우 빠른 정렬 알고리즘.
• 데이터의 개수가 N, 대아터 중 최대값이 K 일 때, 계수 정렬은 최악의 경우에도 수행시간O(N+K)를 보장한다.
• 다만, '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능함.
• 일반적으로 가장 작은 데이터와 가장 큰 데이터가 1,000,000을 넘지 않을 때 효과적으로 이용 가능함.
• 왜냐하면, 계수 정렬시 가장 큰 데이터를 담을 수 있는 범위의 리스트롤 선언해야하기 때문.
• 배열 초기화시 가장 작은 데이터와 가장 큰 데이터의 차이가 1,000,000이라면, 1,000,001로 초기화 해야함.

[시각화]

• 계수 정렬은, 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성함. 아래 예시에서는 가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0'이다.

• 결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됨.
• 5 인덱스의 값이 2이므로 '5'는 2번 등장한 것. 이 리스트에 저장된 데이터 자체가 정렬된 형태를 띔

 

[계수 정렬 소스코드]

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 # 각 데이터에 해당하는 인덱스의 값 증가

# 리스트에 기록된 정렬 정보 확인
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

[계수 정렬의 시간 복잡도]

O(N+K)