Sorting Algorithm - 계수정렬 (counting sort)

• 계수정렬은 최소값과 최대값의 차이가 1,000,000(백만)을 넘지 않을때 효과적인 정렬방식이다.
• 계수정렬은 값을 비교해서 정렬하는 비교기반 정렬방식이 아니다.
• 계수정렬은 최소값 ~ 최대값 범위 개수의 크기의 배열이 필요하다. ( 3 ~ 11 이라면 size=9)
• 시간복잡도는 O(n + k) 이다. (k = 최대값의 크기)

 

 

 

초기상태 : [ 9, 5, 6, 3, 1, 2, 0, 3, 5, 6, 7, 8, 9, 5, 1, 2, 4, 5, 9, 3 ]

배열선언 = 배열의크기 (0~9) = 10

0	1	2	3	4	5	6	7	8	9

 

---

 

각 원소들이 몇개 있는지 세면서(counting) 원소값과 같은 index 위치에 해당 원소값의 개수를 넣어준다.

 

 

<예시>

 

0 이 1개

초기상태 : [ 9, 5, 6, 3, 1, 2, 0, 3, 5, 6, 7, 8, 9, 5, 1, 2, 4, 5, 9, 3 ] 

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

 

1 이 2개

초기상태 : [ 9, 5, 6, 3, 1, 2, 0, 3, 5, 6, 7, 8, 9, 5, 1, 2, 4, 5, 9, 3 ] 

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

 

2 가 2개

초기상태 : [ 9, 5, 6, 3, 1, 2, 0, 3, 5, 6, 7, 8, 9, 5, 1, 2, 4, 5, 9, 3 ] 

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

 

...

 

 

9 가 3개

초기상태 : [ 9, 5, 6, 3, 1, 2, 0, 3, 5, 6, 7, 8, 9, 5, 1, 2, 4, 5, 9, 3 ] 

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

 

정렬하고자 하는 값들에 대해서 각 값의 빈도를 세면서(count) 배열에 입력하고 결과적으로 이 배열에서 차례대로 그 값을 빈도수만큼(배열값) 출력하면 된다.

---

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

출력

0

1 1

2 2

3 3 3

4

5 5 5 5

6 6

7

8

9 9 9

 

출력결과 >>  0 1 1 2 2 3 3 3 4 5 5 5 5 6 6 7 8 9 9 9