계수 정렬(counting sort)

📔 계수 정렬(counting sort) 이란

• 작은 범위 조건이 있는 경우에 한해서 빠른 알고리즘
• 시간복잡도: O(N), 최악의 경우 O(N^2)
• 크기를 기준으로 갯수만 세주면 된다. 비교정렬 X

 

📔 계수 정렬(counting sort) 구현

N = 5  # 5 이하인 수들을 정렬해라
numbers = [1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 3,
           3, 2, 1, 2, 3, 1, 2, 3, 4, 1, 5, 1,
           2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3,
           4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
print(f'정렬 전: {numbers}')
count_list = [0] * (N + 1)

for number in numbers:
    count_list[number] += 1

sorted_numbers = []
for i in range(len(count_list)):
    for j in range(count_list[i]):
        sorted_numbers.append(i)

print(f'정렬 후: {sorted_numbers}')

 

📔 계수 정렬(counting sort) 특징

• 장점
  • 특정 조건에서 매우 빠름 O(N)
  •  
  • 안정 정렬
• 단점
  
  • 범위가 커질수록 메모리 낭비가 심하다.
  • 원래의 시간복잡도는 O(N+K) 여기서 K는 범위중 가장 큰 수
    K가 N보다 커지게 되면 시간복잡도 증가
    만약 10개(N)의 숫자를 비교하는데 가장 큰수가 100(K)이면
    100개를 모두 순회해야하기 때문에 시간복잡도는 O(N^2)