계수 정렬

선택, 삽입, 퀵 정렬에 이어서 마지막으로 계수 정렬에 대해 공부해 보자.

 

계수 정렬(Count Sort)

계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작한다.

 

계수 정렬은 모든 데이터가 양의 정수일 때 데이터의 개수가 N개, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)의 수행 시간을 보장한다.

 

하지만 한 가지 조건이 붙는데, 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬이 이러한 특징을 가지는 이유는 계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 배열을 선언해야 하기 때문이다.

 

계수 정렬은 선택, 삽입, 퀵 정렬처럼 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식인 비교 기반의 정렬 알고리즘이 아니다.  계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

 

이름에서 알 수 있는 것처럼, 새로 생성한 배열에는 각 정수가 몇 개 들어있는지 개수를 세서 넣어주면 된다. 

 

일단, Input Data에서 최댓값을 찾고, 최댓값+1개의 배열을 선언하고 0으로 초기화한다.

그다음엔 데이터를 한 번돌면서 각 숫자에 해당하는 새로운 배열의 인덱스에 1씩 더해주기만 하면 된다.

##메인 함수 부분##
if __name__ == "__main__":
    #모든 원소의 값이 0보다 크거나 같다고 가정
    array = [7,5,9,0,3,1,6,2,4,8,0,5,2]
    #모든 범위를 포함하는 리스트 선언(0으로 초기화)
    count = [0]*(max(array)+1)

    for i in range(len(array)):
        count[array[i]] += 1 #각 데이터에 해당하는 인덱스에 1씩 증가

    for i in range(len(count)):
        for j in range(count[i]):
            print(i, end=" ")
        #앞서 했던 정렬은 배열 안의 숫자의 위치를 바꾸는 비교 기반의 정렬 알고리즘이기 때문에
        #배열 안에서 정렬이 되기 때문에 개행이 필요가 없지만, 계수 정렬은 숫자 만큼 출력하기 때문에
        #개행과 함께 출력이 필요하다.

 

시간 복잡도

처음에 얘기했지만 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터의 최댓값이 K라고 할 때, 최악의 경우에도 O(N+K)를 보장한다. 한 번 돌면서 리스트에서 인덱스의 값에 1씩 더하고, 해당하는 값을 확인할 때 데이터의 최댓값만큼 반복하기 때문이다. 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있고, 항상 빠르게 동작한다.

현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)와 더불어 가장 빠르다고 한다. 기수 정렬은 처리할 수 있는 정수의 크기가 더 크지만 알고리즘과 소스코드도 더 복잡하고 계수 정렬보다 느리게 동작한다. 코딩 테스트에서는 거의 출제되지 않는다고 한다.

 

공간 복잡도

배열을 최댓값의 크기만큼 선언을 한다는 것에서 예상을 했겠지만, 계수 정렬은 때에 따라 심각한 비효율성을 초래할 수 있다. 데이터가 만약 0과 999,999 두 개만 있다고 하는 경우에도 크기가 1,000,000인 배열을 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니고, 동일한 값을 가지는 데이터가 여러개 등장할 때 적합하다. 데이터의 특성을 파악하기 어려운 경우라면 퀵 정렬을 이용하는 것이 유리하다.

 

정리하면, 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 하지만 조건만 만족한다면 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있다는 장점이 있다.

일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간문제로 인해 입력되는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서의 데이터 개수는 1,000만 개 미만으로 출제된다고 한다. 계수 정렬의 공간 복잡도 또한 O(N+K)이다.