이코테-chapter6: 계수 정렬

정리 내용

계수 정렬

• count sort
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
• 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다.
• 일반적으로 max와 min의 차이가 1,000,000을 넘지 않을 때, 효과적으로 사용할 수 있다.
• 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 O(N+K)를 보장한다.
• 현존하는 정렬 알고리즘 중에서 데이터의 범위만 한정되어 있다면 기수 정렬(radix sort)와 더불어 가장 빠르다.
• ex) [0, 999999] 이런 상황에서는 계수 정렬 사용 x => 리스트의 크기가 100만 개가 되도록 선언해야 해서 비효율적임.
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합 ex) 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 이런 경우에선 효율적임.

계수 정렬 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
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=' ')

출처 && 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github