[python] 계수정렬

카운트 할 배열을 선언하고, 정렬할 배열 요소가 몇개가 있는지 카운트 배열 각 인덱스에 담는다
데이터의 크기가 한정되어  빠르게 동작해야할 때 사용된다.

 

예제를 통해   [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 배열을 

순서대로 정렬해보자

 

step 0 배열과 요소의 갯수를 셀 배열 선언

arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

cnt = [0] * (max(arr) + 1) # arr 변수에 요소가 몇개가 있는지 셀 배열

 

step 1

arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	1	0	0

 

step 2

arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	0

 

--과정 반복--

arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

"0" 인덱스 값이 2이므로 0을 2번 출력,  "1" 인덱스 값이 2이므로 0을 2번 출력

다음과정을 반복하면 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 출력된다

 

 

 

 

arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
cnt = [0] * (max(arr) + 1) #카운트 할 배열

for i in range(len(arr)):
  cnt[arr[i]] += 1 # for문을 돌며 각 데이터에 해당하는 인덱스 값을 +1 한다

for i in range(len(cnt)): #len(cnt)는 10이다
  for _ in range(cnt[i]):#cnt의 인덱스 하나를 돈다.
    print(i, end = " ") #i를 cnt의 값만큼 반복 출력하고 빠져나와 그 다음 i+1번째 인덱스로 이동한다

 

출력결과

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

 

 

장점

정렬 알고리즘	평균시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때 빠름
퀵 정렬	O(NlogN)	O(N)	대부분의 경우 가장 적합, 충분히 빠름
계수 정렬	O(N + K)	O(N + K)	데이터의 크기가 한정되었을 때문 사용, 매우 빠름

다음표에서 확인할 수 있듯이, 

데이터의 크기가 한정되었을 때, 매우 빠르게 동작하는 특징이 있다.