[Algorithm] 계수 정렬

※ 계수 정렬?

크기를 기준으로 세는 알고리즘

 

계수 정렬은 '범위 조건'이 존재하는 경우에 한해 굉장히 빠른 알고리즘이다. 다음의 5 이하 자연수 데이터들을 오름차순으로 계수 정렬해보자.

 

 

[1,3,2,4,3,2,5,3,1,2,3,4,4,3,5,1,2,3,5,2,3,1,4,3,5,1,2,1,1,1]

 

 

<정렬 과정>

1) 1부터 5까지 숫자의 개수를 셀 list를 만든다.

2) 데이터 셋을 돌면서 나오는 숫자에 해당하는 count를  +1 해준다.

3) 각각 count 한만큼 반복하여 출력(또는 list 원소 추가)한다.

 

 

 

이를 Python으로 구현한 Code는 다음과 같다.

 

[Python Code 👩🏻‍💻]

 

data_set = [1,3,2,4,3,2,5,3,1,2,3,4,4,3,5,1,
            2,3,5,2,3,1,4,3,5,1,2,1,1,1]

count = [0]*5

result_set = []

for i in data_set:
    count[i-1] +=1

for i in range(len(count)):
    if (count[i] != 0):
        for j in range(count[i]):
            result_set.append(i+1)
            
print(count)
print(result_set)

Code Review >

1 ) 첫 번째 for문을 통해 1~5까지의 각 개수를 count 한다.

2 ) 두 번째 for문을 통해 count가 0이 아니라면 그 수만큼 해당 숫자를 list에 추가한다.

 

 

위와 같이 구현하고 보니 python 내 count 함수로 구현하면 더 쉽게 구현이 될 것 같아서 시도해보았다.

 

[두 번째 Python Code 👩🏻‍💻]

 

data_set = [1,3,2,4,3,2,5,3,1,2,3,4,4,3,5,1,
            2,3,5,2,3,1,4,3,5,1,2,1,1,1]

result_set = []

for i in range(6):
    if(data_set.count(i+1) !=0):
        for j in range(data_set.count(i+1)):
            result_set.append(i+1)

print(result_set)

Code Review >

1 ) count 함수를 이용하여 바로 각 숫자의 개수를 센 다음 for문을 통해 count 한 개수만큼 result_set list에 숫자를 추가시킨다.

 

 

계수 정렬의 시간 복잡도는?

 

위 정렬에서 데이터의 크기가 1~5라는 점에서 반복문 자체도 1부터 5까지만 반복한다는 것을 알 수 있다. 모든 데이터의 크기를 메모리 상에 표현할 수만 있다면 O(N)의 속도로 정렬을 수행할 수 있다.