정렬 알고리즘 : 계수 정렬 (Python)

계수 정렬

---

계수정렬 gif

 

개념

- 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 매우 빠른 정렬 알고리즘이다.

- 특정한 조건 : 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. ex. 0 이상 100 이하인 성적 데이터를 정렬

- 이유 : 모든 데이터 범위를 담을 수 있는 리스트를 선언

- 비교 기반의 정렬 알고리즘 X (선택, 삽입, 퀵 정렬 처럼 데이터를 비교하며 위치를 변경하지 않음)

 

소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언 및 0으로 초기화
# ex. 최댓값이 9일 경우, 0 ~ 9 므로 9 +1 = 10
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=' ')

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

1) 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.

2) 리스트의 모든 원소를 0으로 초기화한다.

3) 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 값을 1씩 증가시킨다.

4) 결과적으로 리스트에 각 데이터가 몇 번 동작했는지 그 횟수가 기록된다.

5) 리스트의 첫 번째 데이터부터 하나씩 그 횟수만큼 인덱스를 출력한다. (데이터가 정렬된 것을 확인할 수 있다.)

 

 

시간복잡도

O(N+K) (N : 데이터 개수, K : 데이터 중 최대갑의 크기)

 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다. 

 

 

공간복잡도

O(N+K)

 상황에 따라 심각한 비효율성을 초래할 수 있다. 반면에 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.