알고리즘 / 계수 정렬

학습 도서

이것이 코딩테스트다 with 파이썬 (한빛미디어, 나동빈 저)

 

 

정렬(Sorting)

 

- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

- 예시 : 오름차순, 내림차순

- 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 

 

계수 정렬(Count Sort)

 

- 시간 복잡도(데이터의 개수 N, 데이터 최댓값 K) : O(N+K)

- 한계 : 데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때에만 사용 가능

- 컨셉 : 데이터의 개수 만큼의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.

- 알고리즘

 1) 데이터 값의 개수를 원소로 가지고 있는 리스트를 선언한다.

 2) 배열의 첫 번째 데이터를 확인한다.

 3) '배열의 첫 번째 데이터'를 인덱스로 가지는 데이터에 1을 더한다.

 4) 배열의 두 번째 데이터를 확인한다.

 5) '배열의 두 번쨰 데이터'를 인덱스로 가지는 데이터에 1을 더한다.

 ...

위와 같은 방법으로 각 데이터가 몇 번씩 등장하는 지 알아보았다. 

이제 그 횟수 만큼 각 데이터를 출력하면, 기존에 주어진 모든 데이터를 오름차순으로 정리할 수 있다.

 

 

전체 소스 코드

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

count = [0]*(max(array)+1)  # [0,0,0,0,0,0,0,0,0,0]


for i in range(len(array)):  # i = 0,1,2,3,4,...,10
    count[array[i]] += 1


for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

 

 

해설

 

코드를 차근차근 살펴보자.

 

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

- Goal : 데이터를 오름차순으로 정리하자.

 

count = [0]*(max(array)+1) 

- [0,0,0,0,0,0,0,0,0,0]

- 데이터의 값은 0부터 9까지 분포해있다.

- max(array) = 9

- 데이터 값으로 0도 가지므로, max(array)+1 만큼의 데이터를 가지는 리스트를 생성한다.

- 아직 수를 세기 전이므로 리스트의 모든 데이터는 0으로 초기화한다.

 

for i in range(len(array)):  
    count[array[i]] += 1

- range(len(array)) = [0, 1, 2, ..., 9]

(포스팅 참고 :   1y9u9j2in.tistory.com/152?category=910442 )

- i = 0, array[0] = 7

  count[7] = 1

  리스트의 첫 번째 데이터가 7 이므로, count 리스트의 7번 째 값에 1을 더한다.

- i = 1, array[0] = 5

  count[5] = 1

  리스트의 두 번째 데이터가 5 이므로, count 리스트의 5번 째 값에 1을 더한다.

...

- count = [2,2,2,1,1,2,1,1,1,2]

 

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

- range(len(count)) = [0, 1, ..., 9]

- i= 0, range(count[0]) = [0, 1]

  0을 2번 출력

- i = 1, range(count[1]) = [0, 1]

  1을 2번 출력

- i = 2, range(count[2]) = [0, 1]

  2를 2번 출력

...

 

최종 출력 결과 = 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9