[Python] 정렬 / 계수 정렬(Counting Sort)

Counting Sort

Counting Sort란 값의 발생 횟수를 계산하는 누적 카운트를 사용하며,
누적 카운트를 갱신해서 순서대로 숫자를 배치하는 방식입니다.


Counting Sort는 배열 내의 최댓값 + 1 만큼의 배열 길이가 필요하므로
정수의 범위가 크면 매우 비효율 적입니다.

파이썬에 내장된 collections.defaultdict 모듈의 딕셔너리 타입을 활용하여 구현해보겠습니다.

defaultdict를 활용한 Counting Sort

from collections import defaultdict

def count_sort_dict(seq):

    result = []
    dic = defaultdict(list)

    # c의 key값(x)에 x를 append -> 각 key에는 x의 갯수만큼 x값이 append
    for num in seq:
        dic[num].append(num)

    # c의 key값의 최소값부터 최대값까지 extend 반복
    # -> 각 key에는 x값의 갯수만큼 x가 list형태로 저장되어 있으므로 extend
    for i in range(min(dic), max(dic) + 1):
        result.extend(dic[i])

    print(result)

seq = [3, 5, 2, 6, 8, 1, 0, 3, 6, 2, 5, 4, 1, 5, 3]
count_sort_dict(seq)

 

dic 딕셔너리는 배열의 원소 x가 key값이 되고, 그 key값은 x의 갯수만큼 x값이 리스트 형태로 저장되어 있습니다.
반복문을 통해 min(), max()를 이용하여 dic의 가장 작은 key값부터 가장 큰 key값 까지
key에 해당하는 리스트를 결과리스트에 extend를 해주면 오름차순으로 정렬이 됩니다.

 

정렬 전 : [3, 5, 2, 6, 8, 1, 0, 3, 6, 2, 5, 4, 1, 5, 3]
정렬 후 : [0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 8]