계수 정렬(Counting Sort) 알고리즘

이번에는 계수 정렬(Counting Sort) 알고리즘에 대해 알아보겠습니다!

 

지난 포스팅의 기수 정렬(Radix sort)와 마찬가지로 비교기반 정렬이 아닌 특수한 정렬 인데욥!

이로인해 기수 정렬(Radix sort)처럼 이론상 비교정렬의 하한 시간복잡도인 O(nlogn)을 뛰어넘는 정렬알고리즘입니다!

https://hipposdata.tistory.com/105

비교정렬 시간 성능의 하한(lower bound): O(nlogn)

 

# 동작과정 

계수 정렬은 특정한 상황을 만족할 시에 사용가능한데욥

값의 범위를 알고 있어야 합니다!

 

총 2가지의 과정을 통해 동작합니다 

1. counting 배열만들기 (입력 배열 순회)

배열의 각 인덱스에 실제 값의 등장횟수만큼 해당하는 값을 증가시킴

 

2. 출력 (counting 배열 순회)

해당 인덱스( =실제 값)를 인덱스의 값(=실제 값의 등장 횟수)만큼 출력

 

예) 4,2,2,8,3,1 값을 오름차순으로 정렬해보겠습니다!

# Python 코드

앞서 설명한 2가지 동작과정을 기반으로 코드를 작성하면 됩니다!

arr = [4, 2, 2, 8, 3, 3, 1] # 입력 배열 arr

count = [0] * (max(arr) + 1) # counting 배열 생성

# 1. counting 배열만들기 (입력 배열 순회)

for i in range(len(arr)):

    count[arr[i]] += 1

# 2. 출력 (counting 배열 순회)

for i in range(len(count)):

    for j in range(count[i]): # counting 배열 값만큼 출력

        print(i, end=' ')

 

# 성능분석 - 시간복잡도

O(n+k)로 매우 빠른 성능을 보여줍니다

n= 입력 값의 길이

k= 입력 값의 범위

 

동일한 값이 여러개 존재할 경우 정렬시 유리함

값의 범위가 클 경우 (k가 커짐) 불리함 -> k만큼의 추가적인 공간 생성 필요함 (메모리 사용 커짐)

 ex) 0, 999999 값 2개 존재시, 값은 2개이지만 100만개 배열 생성해야함 -> 비효율적 

# reference

이것이 취업을 위한 코딩 테스트다 with 파이썬. (2020). (n.p.): 한빛미디어.