계수(카운팅) 정렬 (Counting sort) with 파이썬(Python)

카운팅 정렬, 혹은 계수 정렬은 O(n + k)의 시간복잡도를 가진 정렬이다.

 

여기서 다소 낯선 k는 정렬을 수행할 배열의 가장 큰 값을 의미한다.

 

k가 단순히 상수로 취급되어 생략되지 않고 남아있는 것은 그만큼 k에 따라 수행시간에 영향을 미치기 때문이다.

 

만약 k가 n보다 작다면 정렬의 수행시간은 O(n)이 되겠지만, 무한대로 크다면 정렬의 수행시간도 무한대가 된다.

 

작동 방식

1. 배열을 이용한 방식

 

계수 정렬은 counting이라는 말 답게 배열에 존재하는 수의 개수를 세어주고, 이 정보를 바탕으로 정렬을 수행한다.

 

그리고 여기서 수와 수의 개수는 배열 혹은 딕셔너리의 인덱스와 해당 값을 통해서 기록할 수 있다.

 

먼저 배열을 통한 계수 정렬은 누적합의 개념을 적용하여 구현할 수 있다.

 

배열을 이용한 계수 정렬의 구현 방식은 다음 단계를 따른다.

 

1. 배열에 존재하는 값의 각 원소의 개수를 세어줄 새로운 배열 count를 만들어준다.

•  count의 길이는 원소의 최대값까지를 인덱스로 사용할 수 있도록 원소의 최대값 + 1 만큼으로 정해준다.
•  count[i] 는 숫자 i가 배열에 몇 개 존재하는지에 대한 정보를 담는다.

# 정렬을 수행할 배열
arr = [4, 7, 9, 1, 3, 5, 2, 3, 4]

count = [0] * (max(arr) + 1)

for num in arr:
    count[num] += 1
    
print(count)

# [0, 1, 1, 2, 2, 1, 0, 1, 0, 1]

 

2. count 배열의 원소를 누적합 값으로 갱신해준다. 이 작업은 arr에 담긴 원소를 바로 정렬된 위치로 삽입하기 위한 사전작업이다.

for i in range(1, len(count)):
    count[i] += count[i-1]

print(count)

# [0, 1, 2, 4, 6, 7, 7, 8, 8, 9]

 

3. arr의 길이와 같은 result 배열을 만들어준다. 해당 배열에는 arr의 원소를 정렬된 위치에 삽입할 것이다.

 

4. arr의 각 원소값을 count의 인덱스로 사용해 값을 가져온 후, 해당 값을 다시 result의 인덱스로 사용해 arr의 원소로 저장해준다.

 

5. 해당 작업을 마친 후 count[arr[i]]의 값을 1 줄여준다.

 

3 ~ 5번 과정을 코드로 옮기면 다음과 같다.

result = [0] * (len(arr))

for num in arr:
    idx = count[num]
    result[idx - 1] = num
    count[num] -= 1

print(result)

# [1, 2, 3, 3, 4, 4, 5, 7, 9]

* result에 값을 삽입하는 과정에서 idx 대신 idx - 1을 사용한 것은, 인덱스가 0부터 시작하기 때문으로 이해하면 된다.

 

해당 과정을 모두 거치면 정렬된 arr의 값을 얻을 수 있다.

 

전체 코드

# 정렬을 수행할 배열
arr = [4, 7, 9, 1, 3, 5, 2, 3, 4]

count = [0] * (max(arr) + 1)

for num in arr:
    count[num] += 1
    
for i in range(1, len(count)):
    count[i] += count[i-1]

result = [0] * (len(arr))

for num in arr:
    idx = count[num]
    result[idx - 1] = num
    count[num] -= 1

print(result)

# [1, 2, 3, 3, 4, 4, 5, 7, 9]

 

2. 딕셔너리를 사용한 방식

 

딕셔너리를 이용해서도 계수 정렬을 사용할 수 있다.

 

딕셔너리를 사용하게 되면, 배열의 원소 - 해당 원소의 개수의 관계를 key와 value 쌍으로 나타낼 수 있다.

 

딕셔너리를 이용한 코드는 다음과 같다.

 

# 정렬을 수행할 배열
arr = [4, 7, 9, 1, 3, 5, 2, 3, 4]

count_dict = {}

for num in arr:
    if num in count_dict:
        count_dict[num] += 1
    
    else:
        count_dict[num] = 1

result = []

for num in range(max(arr) + 1):
    while num in count_dict and count_dict[num] != 0:
        result.append(num)
        count_dict[num] -= 1

print(result)

 

계수 정렬의 단점

계수 정렬은 정렬하고자 하는 배열의 최대값이 매우 클 때 메모리를 매우 비효율적으로 쓰게 된다는 단점이 있다.

 

앞서 설명했듯, 배열에 존재하는 원소의 개수를 기록해주기 위해선 크기가 원소의 최대값인 count 배열을 만들어줘야했다.

 

그리고, 만약 우리가 정렬하고자 하는 배열이 [3, 491820395] 라고 가정해보자.

 

해당 케이스에서 계수 정렬을 사용할 경우, 숫자가 단 두 개임에도 불구하고 491820395 만큼의 count 배열을 만들어줘야한다.

 

이는 매우 메모리적으로 비효율적이다.

 

 

또한, count 배열의 인덱스를 통해서 숫자의 개수를 세어주는 방식이기 때문에, 만약 배열에 음수가 존재한다면 사용할 수 없다는 단점도 존재한다.