1. 계수 정렬 개념
배열에 존재하는 원소 중 최대값을 범위로 가지는 새로운 배열을 만들어, 각 원소의 개수를 기록해 놓음으로서 선형 시간 내에 정렬을 할 수 있습니다.
계수 정렬을 안정적인 정렬로 이용하기 위해서 누적합을 계산하여 원소들의 위치를 지정합니다.
기수 정렬과 마찬가지로 비교 기반 정렬 알고리즘이 아닙니다.
원소의 범위가 넓을수록 원소의 개수를 관리할 배열의 크기가 커지므로, 원소의 범위가 좁은 특별한 상황에서 사용됩니다.
2. 계수 정렬 예제
4, 2, 2, 8, 3, 3, 1 을 정렬해봅시다.
각 원소의 개수를 기록합니다.
기록된 개수의 누적합을 계산합니다.
누적합 결과는 각 원소의 정렬 후 위치가 될 것입니다.
기존 배열의 뒤에서부터 원소를 새로운 자리에 위치시킵니다.
새로운 자리의 위치는 누적합한 결과값이 되고, 자리하면서 누적합 값을 1 감소시킵니다.
남은 수를 반복합니다.
3. 계수 정렬 코드
nums = [4, 2, 2, 8, 3, 3, 1]
def counting_sort(nums):
# 원소의 최대값 확인
max_num = max(nums)
# 계수 배열의 크기를 원소의 최대값만큼 설정
count = [0] * (max_num+1)
# 각 원소의 개수를 셈
for num in nums:
count[num] += 1
# 누적합 계산
for i in range(max_num):
count[i+1] += count[i]
# 기존 배열의 역순으로 탐색하여 정렬
tmp = [0] * len(nums)
for i in range(len(nums)-1, -1, -1):
tmp[count[nums[i]]-1] = nums[i]
count[nums[i]] -= 1
for i in range(len(nums)):
nums[i] = tmp[i]
counting_sort(nums)
print(nums)
# [1, 2, 2, 3, 3, 4, 8]4. 계수 정렬 장점
시간 복잡도가 \(O(n)\)으로 매우 효율적인 알고리즘입니다.
계수 정렬은 안정적인 정렬로, 동일한 값을 가지는 원소의 상대적인 순서가 유지됩니다.
5. 계수 정렬 단점
계수 배열을 위한 추가적인 메모리가 필요합니다.
게다가 데이터의 범위가 크면 계수 배열을 만들 수가 없어 사용이 불가능합니다.
6. 정렬 알고리즘 시간 복잡도 비교
| 정렬 알고리즘 | 최악(Worst) | 최선(Best) | 평균(Average) |
| 버블 정렬(Bubble Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 선택 정렬(Selection Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 삽입 정렬(Insertion Sort) | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) |
| 퀵 정렬(Quick Sort) | \(O(n^2)\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 병합 정렬(Merge Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 힙 정렬(Heap Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 기수 정렬(Radix Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
| 계수 정렬(Counting Sort) | \(\boldsymbol{O(n)}\) | \(\boldsymbol{O(n)}\) | \(\boldsymbol{O(n)}\) |
