1. 도수 정렬이란?
도수 정렬(Counting Sort)은 비교 연산을 사용하지 않고 정렬하는 알고리즘이다. 각 숫자의 등장 횟수를 세어 정렬하는 방식으로 동작하며, 특히 데이터의 크기 범위가 제한적이고 정수 값으로 표현될 때 효율적으로 사용할 수 있다.
2. 도수 정렬의 원리
도수 정렬은 다음 4단계로 이루어진다:
- 도수 분포표 생성 → 각 숫자가 몇 번 등장하는지 세어 저장한다.
- 누적 도수 분포표 생성 → 각 숫자의 위치를 결정할 수 있도록 누적합을 구한다.
- 정렬된 배열 생성 → 입력 배열을 순회하며 정렬된 위치에 값을 배치한다.
- 배열 복사 → 정렬된 데이터를 원래 배열에 복사한다.
이제 파이썬 코드와 함께 자세히 살펴보자!
3. 도수 정렬 구현
from typing import MutableSequence
def counting_sort(a: MutableSequence) -> None:
n = len(a) # 배열의 크기
f = [0] * (max(a) + 1) # 도수 분포표(Count 배열)
b = [0] * n # 정렬된 데이터를 저장할 보조 배열
# 1단계: 도수 분포표 생성
for i in range(n):
f[a[i]] += 1
# 2단계: 누적 도수 분포표 생성
for i in range(1, max(a) + 1):
f[i] += f[i - 1]
# 3단계: 정렬된 배열 생성 (뒤에서부터 처리)
for i in range(n - 1, -1, -1):
f[a[i]] -= 1
b[f[a[i]]] = a[i]
# 4단계: 정렬된 데이터 원본 배열에 복사
for i in range(n):
a[i] = b[i]
f[a[i]] -= 1을 하는 이유는 0-based index이기 때문에 기본적으로 -1을 처리하며, 다음에 같은 숫자가 중복될 때, 다음 숫자의 위치를 한 칸씩 앞으로 이동하는 역할을 한다.
4. 도수 정렬 과정 예제
예제: a = [1, 4, 1, 2, 7, 5, 2]를 도수 정렬로 정렬해보자.
-
도수 분포표 생성 (각 숫자의 개수를 저장)
f = [0, 2, 2, 0, 1, 1, 0, 1] # 1이 2번, 2가 2번, 4가 1번, 5가 1번, 7이 1번 등장 -
누적 도수 분포표 생성 (누적합을 구하여 각 숫자의 위치 결정)
f = [0, 2, 4, 4, 5, 6, 6, 7] # 1의 마지막 위치는 2번째 인덱스, 2의 마지막 위치는 4번째 인덱스... -
정렬된 배열 생성 (뒤에서부터 채워 넣기)
b = [1, 1, 2, 2, 4, 5, 7] # 정렬된 결과 -
배열 복사 → 최종적으로
a가[1, 1, 2, 2, 4, 5, 7]로 정렬됨.
5. 도수 정렬의 시간 복잡도
| 경우 | 시간 복잡도 |
|---|---|
| 최선 | O(n + k) |
| 평균 | O(n + k) |
| 최악 | O(n + k) |
n: 정렬할 데이터의 개수k: 데이터의 최댓값- 비교 기반 정렬이 아니기 때문에 O(n log n) 보다 빠를 수도 있다!
6. 도수 정렬의 특징 및 한계
✅ 도수 정렬의 장점
- 비교 연산이 필요 없음 → 정렬 속도가 빠르다.
- O(n + k)의 성능 보장 → 입력 크기에 비례하는 성능을 유지.
- 안정 정렬(Stable Sort) → 동일한 값의 순서가 유지됨.
❌ 도수 정렬의 단점
- 추가적인 메모리 사용 → O(k) 크기의 배열이 필요하여 메모리 사용량이 많다.
- 데이터의 범위가 클 경우 비효율적 →
k가 크면 공간 낭비가 심해진다. - 실수(float)나 음수 처리 어려움 → 정수 정렬에 적합하다.
7. 마무리
- 도수 정렬은 정수 데이터를 정렬할 때 매우 효율적이다.
- 하지만 데이터 크기가 크거나 범위가 클 경우 비효율적일 수 있다.
- 추가적인 공간을 필요로 하기 때문에 메모리 제한이 있는 환경에서는 주의가 필요하다.
도수 정렬을 활용할 때는 정렬하려는 데이터의 특성을 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요하다! 😊
꾸준함을 잃지 말자.