[알고리즘] 정렬 알고리즘(Sorting)(3) - 계수 정렬

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘

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

 

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

 

 

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트 초기화

2. 각 인덱스가 데이터의 값에 해당

3. 각각의 데이터가 총 몇 번씩 등장했는 지 개수를 세면 됨

4. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 (Count)

 

 

5. 결과를 확인할 때 리스트이 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스 출력

 

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

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

 

계수 정렬의 복잡도

 

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(K+K)

계수 정렬은 때에 따라 심각한 비효율성 초래할 수 있음

(데이터가 0과 999,999로 단 2개만 존재하는 경우에도 -> 총 1,000,000 크기의 원소 배열이 필요)

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

(성적의 경우 100점 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬에 효과적)

 

정렬 알고리즘 비교

대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있음! -> 정렬 함수를 구하라는 조건이 없다면, 표준 정렬 라이브러리 호출해서 사용하는 것을 추천