계수정렬(CountingSort) 이론과 파이썬 구현

계수정렬(CountingSort)

 

계수정렬은 n이 정수면 입력 값들이 1부터 n까지의 정수라는 가정이 필요합니다.

그리고 입력 값들을 갯수만큼 세서 출력해주면 정렬을 할 수 있습니다.

 

속도가 빠르고 코드가 간결하다는 장점이 있습니다.

 

계수정렬을 이용한 전체 정렬 과정

 

기존 리스트의 요소를 하나씩 검사하여 새로운 리스트에 그 요소의 위치에 값을 1씩 더해줍니다.

검사를 완료하면 새로운 리스트의 갯수들을 그 위치의 숫자만큼 출력해줍니다.

 

계수정렬의 파이썬 코드입니다.

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

n=[0] * 5
a=[]

for i in range(len(b)):
    n[b[i]-1] += 1

for i in range(len(n)):
    for j in range(n[i]):
        a.append(i+1)
            
# 결과>>[1, 1, 2, 3, 4, 4, 4, 5]
print(a)