[Algorithm] (이코테) 정렬 - 계수 정렬(Count Sort) (Python/파이썬)

▶ 문제 설명

계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단하다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 예를 들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때 계수 정렬이 효과적이다. 다만, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다. 계수 정렬이 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언'해야 하기 때문이다. 예를 들어 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000 이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화해야 한다. 여기에서 1개를 더해주는 이유는 0부터 1,000,000까지는 총 1,000,001개의 수가 존재하기 때문이다.

계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하면 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다. (선택 정렬, 삽입 정렬, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 정렬 방법을 비교 기반의 정렬 알고리즘이라고도 부른다.)

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 구체적인 예시를 통해 계수 정렬에 대해서 이해해보자. 단, 말했듯이 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작한다. 따라서 예시 또한 앞서 다루었던 예시와 다르게 많은 데이터가 존재하는 경우를 살펴보자.

 

- 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

 

계수 정렬은, 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 현재 예시에서는 가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0' 이다. 따라서 우리가 정렬할 데이터의 범위는 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다. 다시 말해 우리는 단순히 크기가 10인 리스트를 선언하면 된다. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화한다. 그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

---

▶ Code

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 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, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

▶ Point

1 ) 계수 정렬의 시간 복잡도

• 앞서 언급했듯이 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K) 이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기만큼 반복을 수행해야 하기 때문이다. 따라서 데이터의 범위만 한저오디어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.
• 보통 기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다. 다만 알고리즘 원리나 소스코드는 더 복잡하다. 다행히 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 코딩 테스트에서 거의 출제되지 않으므로, 책에서는 기수 정렬에 대해서 자세히 다루지는 않는다.

2 ) 계수 정렬의 공간 복잡도

• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999, 단 2개만 존재한다고 가정해보자. 이럴 때에도 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합한다. 예를 들어 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다. 반면에 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.
• 다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있다. 다만 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 인하여 입력되는 데이터의 개수를 1,000만개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서의 데이터 개수는 1,000만 개 미만으로 출제될 것이다. 계수 정렬의 공간 복잡도는 O(N + K)이다.