[이코테] CHAPTER 06 정렬 - 계수 정렬

계수 정렬 (Count Sort)

: 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘( 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.)

별도의 리스트를 선언하고 그 안에 정보를 담는다.

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완성된다.

ex)

    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

    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

    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	1

    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
1	0	0	0	0	1	0	1	0	1

    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
1	0	0	1	0	1	0	1	0	1

    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
1	1	0	1	0	1	0	1	0	1

    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
1	1	0	1	0	1	1	1	0	1

    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
1	1	1	1	0	1	1	1	0	1

 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
1	1	1	1	0	1	1	1	0	2

 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
1	2	1	1	0	1	1	1	0	2

 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
1	2	1	1	1	1	1	1	0	2

 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
1	2	1	1	1	1	1	1	1	2

 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	1	1	1	1	1	1	1	2

 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	1	1	1	2	1	1	1	2

 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번, 1은 2번,이런식으로 출력된다.

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

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=' ')

데이터의 개수는 N개, 데이터 중 최대값의 크기를 K => 시간 복잡도 O( N+ K )