도수 정렬 [ 크래프톤 정글 9일차 ]

도수 정렬(Counting Sort)은 이름이 낯설지만 한 번 쯤 작성해본 적이 있을 수 있는 정렬입니다.

배열의 요소가 정수이고, 특정 범위 내에 있을 때 매우 빠른 성능을 보이는 알고리즘이예요.

예를 들어서 숫자 1~9가 있는 문자열 s 가 있다고하자.

문자열 S = '123456789876553457683454514273515146734'

이 중에서 1이 등장(도수)한 횟수, 2가 등장한 횟수 3이 등장한횟수,,, 9가 등장한 횟수를 세어야 한다고 할 때, 좋다.

우선 INDEX 9 까지 있는 배열을 생성하고 1 2 3 4 5 등 숫자가 등장할 때마다 해당 index 에 1을 더해준다

dosu = [0,0,0,0,0,0,0,0,0]
S = '123456789876553457683454514273515146734'

for i in S:
	dosu[int(i)] += 1

이렇게 보니까 엄청 직관적이지 않나요?

초등학교 다니는 사촌동생 데려와서 설명해도 이해할 수 있는 정도입니다.

물론 좀 더 파이썬스럽게 짜고 싶으면 이런 문법도 있습니다.

from collections import Counter

S = '123456789876553457683454514273515146734'
count = Counter(S)
print(count)

# 출력: Counter({'5': 8, '4': 7, '3': 5, '7': 5, '1': 4, '6': 4, '8': 3, '2': 2, '9': 1})

Counter 함수를 쓰면 딕셔너리 형태로 제공됩니다.

물론 범위 내의 숫자를 셀 때 뿐 아니라

이름이 몇 번 등장 했는지 세는 것도 가능합니다.

from collections import Counter

names = ['Alice', 'Bob', 'Alice', 'Charlie', 'Bob', 'Alice']

count = Counter(names)

print(count)
# 출력: Counter({'Alice': 3, 'Bob': 2, 'Charlie': 1})

이처럼 도수 정렬은 특정 조건을 만족했을 때, 매우 빠른 성능을 보이는 알고리즘이라.
알아두시면 다양한 문제에 마주했을 때, 일반 힙,퀵 정렬 알고리즘 보다도 훨씬 빠르게 정렬을 수행하실 수 있을거예요!