이 글은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 읽고 작성하였습니다.
계수 정렬
1. 계수 정렬 개요
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘입니다.
계수 정렬은 최악의 경우에도 수행시간이 O(N + K)인데, '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있습니다.
예를 들어, 데이터 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우는 사용하기 어렵고, 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있습니다.
데이터의 크기 범위가 제한되는 특징을 가지는 이유는 계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언'해야 하기 때문입니다.
2. 계수 정렬 예시
계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있습니다. 예시를 보며 확인하겠습니다.
초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성합니다.
예시에서는 가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0'이므로 0부터 9까지 모두 포함하기 위해 크기가 10인 리스트를 선언합니다. 그리고 처음에는 리스트의 모든 데이터가 0이 되도록 초기화합니다. 그 후, 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시키면 됩니다.
-
초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
-
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 (0번 인덱스 7의 값을 리스트에서 그 데이터 하나 증가)
-
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 (인덱스를 하나 증가해 1번 인덱스 5의 값을 리스트에서 그 데이터 하나 증가)
-
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 (인덱스를 하나 증가해 2번 인덱스 9의 값을 리스트에서 그 데이터 하나 증가)
과정 반복....
- 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됩니다. 예를 들어 0 인덱스의 값이 2이므로 '0'은 2번 등장한 것입니다. 이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있습니다. 이를 확인하려면 직접 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 됩니다.
3. 계수 정렬 소스코드
# 모든 원소는 값이 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 입니다.
4. 계수 정렬의 시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)입니다.
계수 정렬은 앞에서부터 데이터를 하나씩 확인하며 리스트에서 적절한 인덱스 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문에 시간 복잡도가 O(N + K)입니다.
따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작합니다.
5. 계수 정렬의 공간 복잡도
계수 정렬은 때에 따라 심삭한 비효율성을 초래할 수 있습니다. 예를 들어, 데이터가 0과 999,999, 단 2개만 존재한다고 할 때 리스트의 크기가 100만 개가 되도록 선언해야 하기 때문입니다.
다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수 없습니다. 하지만 조건을 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있습니다.
계수 정렬의 공간 복잡도는 O(N + K)입니다.
