[알고리즘] 계수 정렬

계수 정렬(Count Sort)

특정한 조건이 부합할 때만 사용할 수 있는 정렬 방법이다. 하지만 매우 빠른 속도를 가지고 있다.

여기서 특정한 조건은 아래와 같다.

1. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있다.

2. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다.

계수 정렬은 가장 큰 데이터와 가장 작은 데이터 차이만큼의 크기를 갖는 리스트를 선언해야 하기 때문에 위와 같은 특정한 조건을 갖는다.

즉, 계수 정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 특징이 있다.

계수 정렬은 모든 범위를 포함하는 인덱스를 갖는 리스트를 생성한 후, 앞에서부터 데이터를 읽어나가며 해당하는 데이터에 맞는 인덱스에 1을 추가한다.

예시

숫자 9, 8, 3, 4, 2, 3, 1, 5, 6, 4, 7이 순서대로 배열에 저장되어 있다.

준비된 데이터

처음 준비된 리스트

준비된 데이터의 최댓값을 9이므로 9까지 저장할 수 있는 리스트를 생성해 준비한다.

앞의 1개의 데이터를 읽었을 때

준비된 데이터의 맨 앞은 9가 저장되어 있다. 따라서 9에 해당하는 인덱스의 크기를 1 증가한다.

앞의 2개의 데이터를 읽었을 때

준비된 데이터의 두 번째에는 8이 저장되어 있다. 따라서 8에 해당하는 인덱스의 크기를 1 증가한다.

모든 데이터를 읽었을 때

위와 같은 방법으로 준비된 모든 데이터를 탐색하면 위와 같은 리스트가 생성된다.

코드

위의 예시를 코드로 알아보자.

array = [9, 8, 3, 4, 2, 3, 1, 5, 6, 4, 7]

# 모든 범위를 포함하는 리스트를 선언하고 0으로 초기화한다.
count = [0] * (max(array)+1)

# 모든 데이터를 확인한다.
for i in range(len(array)):
    # 각 데이터에 해당하는 인덱스의 값을 1 증가시킨다.
    count[array[i]] += 1

# 띄어쓰기를 구분으로 각 데이터의 갯수만큼 출력한다.
for i in range(len(count)):
    for j in range((count[i])):
        print(i, end = '')

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

출력 결과를 보면 인덱스에 저장된 숫자만큼 데이터를 출력하는 것을 알 수 있다.

시간 복잡도

계수 정렬은 데이터를 앞에서부터 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시키는 알고리즘이다. 따라서 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때 계수 정렬의 시간 복잡도는 $O(N+K)$이다.

정리

1. 계수 정렬은 특정한 조건이 부합해야만 사용할 수 있지만 매우 빠르다.

2. 모든 범위를 포함하는 리스트를 생성한 후, 앞에서부터 데이터를 읽어나간다.

3. 계수 정렬은 데이터의 개수를 N, 최댓값의 크기를 K라고 했을 때 O(N+K)의 시간 복잡도를 가진다.