계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
• 데이터의 개수(N), 데이터 중 최댓값(K)일 때, 최악의 경우에도 시간복잡도 O(N+K)를 가진다.

1. 계수 정렬 동작 예시

[Step 0]

출처 : 이코테2021

• 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성한다.
• 총 9개가 필요하다는 말!
• 여기서 인덱스는 특정 데이터의 값이랑 동일시 한다.
• [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2], 15개, min = 0, max = 9

 

[Step 1]

• 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
• 여기선 7이므로 7인덱스를 1증가시킨다.

 

[Step 2]

• 여기서는 5이므로 5의 인덱스를 1증가시킨다.

 

[Step 15]

• 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록된다.
• 결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.
• ex) 인덱스0을 출력할땐 0을 2번, 인덱스 1을 출력할때는 1을 2번...

 

• 이와같이 출력할 수 있다.
• 가장 작은데이터, 가장 큰 데이터 배열만 있으면 모두 가능하다.

---

2. 계수 정렬 소스코드

#모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가
    
for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ')

• 값이 같은 인덱스만큼 1씩 계속 증가시켜준다.

#실행 결과
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

---

3. 계수 정렬의 복잡도 분석

• 시간 복잡도와 공간 복잡도는 모두 이와같다.
• 계수 정렬은 데이터가 0과 999,999 등 단 2개만 존재하는 경우 심각하게 비효율적일 수 있다.
  • 0부터 999,999까지 한 번씩 반복문이 돌아야하기 때문에
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적이다.
  • 성적이 100점인 학생 등.