[Algorithm] 계수 정렬은 뭐야?

계수 정렬의 다른 정렬 알고리즘들과는 다르게 숫자들을 비교하여 정렬하는 알고리즘이 아니다. 그렇다면 어떻게 동작할까? 우선 배열의 최대 숫자보다 1 큰 배열을 생성한다. 그리고 정렬할 배열에 있는 원소를 생성한 배열의 위치 값으로 사용하고, 해당 위치의 값을 1 증가시켜준다. 정렬할 배열의 모든 원소를 확인했다면 생성한 배열의 위치 값과 배열의 값(해당 원소의 개수)을 출력하는 것으로 정렬을 마친다.

 

위와 같이 계수 정렬은 배열을 한 번씩만 확인해주기 때문에 시간 복잡도가 O(N+K)이다. 빠른 시간 복잡도에는 그만큼 전제가 많이 붙는다. 계수 정렬을 사용하기 위한 조건은 다음과 같다.

 

• 배열의 모든 원소들은 0을 포함한 양의 정수여야 한다.
• 최솟값과 최댓값의 차이가 100만을 넘지 않는 것이 좋다.

다음은 0부터 5까지의 숫자를 무작위로 배치한 정보를 계수 정렬을 이용하여 정렬하는 방식이다.

 

계수 정렬 순서 1번째

진한 회색은 정렬되지 않은 배열이고, 노란색은 생성한 배열의 위치 값, 밝은 회색은 생성한 배열의 값이다.

파란색은 정렬을 진행 중인 값이다.

 

계수 정렬 순서 2번째

먼저 가장 앞에 있는 4를 확인한다. 생성한 배열의 4 위치의 숫자를 1 증가시켜준다.

 

계수 정렬 순서 3번째

다음은 생성한 배열의 2 위치의 숫자를 1 증가시켜준다.

 

계수 정렬 순서 4번째

다음은 생성한 배열의 5 위치의 숫자를 1 증가시켜준다.

 

계수 정렬 순서 5번째

다음은 생성한 배열의 1 위치의 숫자를 1 증가시켜준다.

 

계수 정렬 순서 6번째

다음은 생성한 배열의 3 위치의 숫자를 1 증가시켜준다.

 

계수 정렬 순서 7번째

다음은 생성한 배열의 0 위치의 숫자를 1 증가시켜준다.

이렇게 계수 정렬을 마친다. 계수 정렬은 빠른 시간 복잡도를 가지지만 그만큼 조건이 필요하기 때문에 필요한 조건을 잘 생각하고 사용하면 좋을 것 같다.

 

다음은 계수 정렬을 코드로 표현한 것이다.

 

array = [4,2,5,1,3,0]
 
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)

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬