계수 정렬(Counting Sort)

계수 정렬

특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

• '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능하다.
• 다른 정렬 알고리즘처럼 비교 후 위치를 변경하는 방식이 아니다.

 

* 파이썬의 sort()나 sorted() 정렬 라이브러리는 퀵 정렬보다도 더 효과적이므로 
별도의 요구 없이 단순 정렬하는 상황이라면 정렬 라이브러리를 쓰는게 더 좋다.

다만, 데이터의 범위가 한정되어 있으며 빠르게 동작해야 할 때 계수 정렬을 사용하는걸 추천

 

구현

arr = [4, 2, 3, 1]이 있을 때 

arr에서 제일 큰 숫자 + 1 만큼의 길이를 가진 리스트를 하나 준비한다. (이유는 아래에서 설명)

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

arr을 돌며 값 x를 하나씩 꺼내

count[x] 위치의 value를 +1 시켜준다.

 

즉, count는 현재 [0, 0, 0, 0, 0]이고 각각 인덱스가 {0, 1, 2, 3, 4}로 구성되어 있는데

arr의 정렬할 값 => count의 인덱스가 되는 것이다.

 

때문에 arr 내부의 정렬할 원소가 너무 큰 값이면 count의 길이가 끝도 없이 길어져버리니

이 부분을 조심해야한다.

 

그렇게 각각의 값을 뽑아내 그 위치에 +1 시켜주고

마지막에 count를 돌며 해당 인덱스가 몇개 있는지를 체크해 인덱스를 그대로 출력해주면 정렬된 값이 나오게 된다.

 

코드

import random
arr = random.sample(range(100), 10)

def counting_sort(arr):
  count = [0] * (max(arr)+1)

  for i in arr:
    count[i] += 1

  answer = []
  for j in range(len(count)):
    answer.extend([j] * count[j])

  return answer

result = counting_sort(arr)
print(result)