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

4. 계수 정렬 (Count sort)

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

모든 데이터가 양의 정수인 상황을 가정해보자.

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

계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라, 원리 또한 매우 간단하다.

다만 계수정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때' 만 사용할 수 있다.

예를 들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 할 수 있다.

예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때 계수 정렬이 효과적이다.

다만, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다.

계수 정렬이 이런 특징을 가지는 이유는, 계수 정렬을 사용할 때 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언' 해야하기 때문이다.

예를 들어 가장 작은 데이터와 가장 큰 데이터의 차이가 1,000,000라면, 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화 해야한다.

계수 정렬은 앞 게시글에서 다뤘던 3가지 정렬 알고리즘들 처럼 직접 데이터의 값을 비교한 뒤 위치를 변경하여 정렬하는 방식 (비교 기반의 정렬 알고리즘)이 아니다.

계수 정렬의 경우 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

구체적인 예시를 통해 계수 정렬에 대해 알아보자.

1. 가장 큰 데이터와 가장 작은 데이터 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
2. 생성한 리스트의 모든 데이터가 0이 되도록 초기화 한다.
3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

각 단계를 밟으며 직접 확인해보자.

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

step 1️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 2️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 3️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 4️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 5️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 6️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 7️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 8️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 9️ : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 10 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 11 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 12 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 13 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 14 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

step 15 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는 지 그 횟수가 기록된다.

예를 들어 인덱스 9의 값이 2이므로, 9가 2번 등장한 것이다.

이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있다.

정렬된 결과를 직접 눈으로 보고 싶다면, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

따라서 인덱스 0의 값이 2이므로, 2번 출력하면 된다.

[출력]

출력 결과: 0 0

출력 결과: 0 0 1 1

출력 결과: 0 0 1 1 2 2

출력 결과: 0 0 1 1 2 2 3

출력 결과: 0 0 1 1 2 2 3 4

출력 결과: 0 0 1 1 2 2 3 4 5 5

출력 결과: 0 0 1 1 2 2 3 4 5 5 6

출력 결과: 0 0 1 1 2 2 3 4 5 5 6 7

출력 결과: 0 0 1 1 2 2 3 4 5 5 6 7 8

출력 결과: 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

1) countSort.py

# 모든 원소의 값이 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 = ' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

- 출력

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

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

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다.

계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스 값을 1 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야하기 때문이다.

따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.

사실상 현존하는 정렬 알고리즘 중, 기수 정렬 (Radix sort)와 더불어 가장 빠르다고 할 수 있다.

기수 정렬은 계수 정렬에 비해 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다. ( 알고리즘 원리나 소스코드는 더 복잡하다.)

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

계수 정렬은 때에 따라서 심각한 비효율서을 초래할 수 있다.

예를 들어 데이터가 0과 999,999 단 두개만 존재한다고 가정하자.

이럴 때에도 리스트의 크기가 100만개가 되도록 선언해야한다.

따라서 항상 사용할 수 있는 정렬 알고리즘이 아니고, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

예를 들어 성적의 경우 같은 점수를 맞은 학생이 여러 명 일 수 있기 때문에 계수 정렬이 효과적이지만, 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르기 때문에 데이터 특성을 파악하기 어려운 경우 퀵 정렬을 사용하는 것이 더 나을 수도 있다.

다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수 는 없다.

하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때도 효과적으로 사용할 수 있다.

하지만 코테 환경에서는 메모리의 제약과 입출력 시간 문제로 인하여 입력되는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서의 데이터의 개수는 1,000만 개 미만으로 출제될 것이다.

계수 정렬의 공간 복잡도는 O(N + K) 이다.