🥐Counting Sort

orders

① 정렬할 데이터 준비

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

○ 이 때, 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 list를 생성 ○

 

② 왼쪽부터 데이터를 하나씩 확인하며 데이터의 값과 동일한 index의 데이터를 1씩 증가시킨다.

 

③ 오름차순 결과를 확인하기 위해 각 원소의 계수가 저장된 list를 왼쪽 끝부터 돌려 해당 데이터의 값만큼 반복해 인덱스를 출력한다.

 

- 출력 결과 -

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

about Counting Sort

🥐 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠르게 동작하는 정렬 알고리즘. (*특정한 조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용)

 

🥐 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 O(N+K) 보장

(첫 반복문 O(N), 두번째 반복문 O(N+K). 두번째 반복문은 원래 데이터가 들어가 있는 arr를 돌리는 동안, 전체 데이터의 최댓값 K까지 저장되어 있는 계수 정렬 list를 한 바퀴 돌리므로 각각 O(N)과 O(K). 따라서 O(N+K))  

 

🥐 주어진 배열의 최솟값과 최댓값 사이의 숫자를 모두 저장해야 하므로 시간 복잡도와 공간 복잡도 모두 O(N+K) 보장

 

🥐 계수 정렬은 때에 따라서 심각한 비효율성 초래. 예를 들어 데이터가 0과 999999로 단 2개만 존재하는 경우.

 

🥐  계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능

Counting Sort code

🥐 python

arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0]*(max(arr)+1)

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

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ') #0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

examples

★ <백준 10989 B1 수 정렬하기 3> ★

Q. 10,000보다 작거나 같은 자연수임을 활용해 O(N+K)인 특수한 계수 정렬을 사용해야만 풀리는 문제

 

★ <백준 2108 S3 통계학> ★

Q. 최빈값과 중앙값을 구할때 계수 정렬 table 사용. 입력된는 정수의 값이 -4000~4000인 문제

---

이코테