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

계수 정렬(Counting Sort)

계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 중복된 값이 많이 분포돼있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. 카운팅 정렬이라고 하기도 한다. 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다.

 

계수 정렬의 조건은 아래와 같다.

1. 데이터의 크기 범위가 제한된 경우
   
   • ex) 0 ~ 100 까지의 점수를 정렬하는 경우
2. 데이터가 양의 정수인 경우
   • 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함
3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우
   • 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐

 

 

정렬 과정

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력

출처 : https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

출처 : https://spagnuolocarmine.github.io/counting-sort.html

 

 

 

파이썬 코드

리스트 자료형(배열)을 활용

def counting_sort(arr):
    max_arr = max(arr)
    count = [0] * (max_arr + 1)
    sorted_arr = list()
    
    for i in arr:	# 카운팅
        count[i] += 1

    for i in range(max_arr + 1):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

 

 

 

딕셔너리 자료형 활용

def counting_sort(arr):
    count = dict()
    sorted_arr = list()
    
    for i in arr:
        if i in count:
            count[i] += 1
        else:
            count[i] = 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

 

아래는 collections 모듈의 defaultdict를 활용한 버전이다.

from collections import defaultdict


def counting_sort(arr):
    count = defaultdict(int)
    sorted_arr = list()
    
    for i in arr:
        count[i] += 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

 

 

 

 

 

 

 

https://debuglog.tistory.com/68

Python으로 알고리즘 공부 03. 계수 정렬 (Counting Sort)

https://freedeveloper.tistory.com/378

[이것이 코딩 테스트다 with Python] 24강 계수 정렬

https://no-delay-code.tistory.com/163

정렬 알고리즘 : 계수 정렬 (Python)

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dnpc7848&logNo=221439395086 

[Python - 자료구조] Counting Sort(계수 정렬)