05_Counting & Radix Sort

요약

알고리즘	시간 복잡도	비고
Counting Sort	$O(n+k)$	안정, k가 작아야 효율적
Radix Sort	$O(d(n+k))$	d가 상수면 O(n)

1. 비교 정렬의 하한 (Lower Bound)

결정 트리(Decision Tree) 모델을 통해 다음을 증명할 수 있다.

• n개 원소를 정렬하는 모든 경우의 수는 n!개이므로, 결정 트리의 잎(leaf)은 최소 n!개 필요
• 높이 h인 이진 트리의 최대 잎 수는 $2^h$이므로 $n!\le 2^h$
• 양변에 로그를 취하고 스털링 근사 n! > (n/e)ⁿ를 적용하면:
  • $h\ge \lg {\left(\frac{n}{e}\right)}^n=n\lg n-n\lg e=\Omega (n\lg n)$

결론

• 모든 비교 정렬은 Ω(n lg n)이며,

• Heap Sort와 Merge Sort는 점근적으로 최적이다.

• 따라서 선형 시간 $O(n)$에 정렬하려면 비교를 사용하지 않아야 한다.

2. Counting Sort

입력이 0~k 범위의 정수라는 가정이 필요하다.

• 기본 아이디어

  • 각 원소 x에 대해 x보다 작거나 같은 원소의 개수를 세어 위치를 결정

• 저장 공간

  • $A[\mathrm{1..}n]$: 입력
  • $B[\mathrm{1..}n]$: 정렬 결과
  • $C[\mathrm{0..}k]$: 카운팅 배열

• 알고리즘 단계

  1. $C[i]\leftarrow 0$ 으로 초기화
     • $\Theta (k)$
  2. $C[A[j]]++$ 로 각 값의 개수 세기
     • $\Theta (n)$
  3. $C[i]\leftarrow C[i]+C[i-1]$ 누적합 계산
     • $\Theta (k)$
  4. A를 뒤에서부터 순회하며 $B[C[A[j]]]\leftarrow A[j],C[A[j]]--$
     • $\Theta (n)$

• 총 시간 복잡도

  • $\Theta (n+k)$
  • $k=O(n)$이면 $O(n)$

• 특징

  • 비교 기반이 아니므로 Ω(n lg n) 하한과 모순되지 않음
  • 안정 정렬(stable): 같은 값의 상대적 순서가 보존됨

동작 방식 (오름차순 기준)

1. 최댓값 확인
   • 입력 데이터 중 가장 큰 값을 찾아 그 크기만큼의 누적 합을 담을 배열(Count Array)을 생성한다. (크기: 최댓값 + 1)
2. 빈도수 세기
   • 원본 배열을 처음부터 끝까지 순회하며, 각 숫자가 나올 때마다 Count 배열의 해당 인덱스 값을 1씩 증가시킨다.
3. 누적합 계산
   • Count 배열의 값을 누적합 형태로 변환한다.
   • 이 누적합은 각 숫자가 정렬된 배열에서 들어갈 마지막 위치(인덱스)를 결정하는 데 사용된다.
4. 결과 배열 배치
   • 원본 배열의 끝에서부터 역순으로 원소를 확인하며, Count 배열에 기록된 위치에 맞춰 결과 배열(Output Array)에 배치한다.
   • 역순으로 순회하는 이유는 기존의 순서를 보장하는 ‘안정 정렬(Stable Sort)‘을 유지하기 위함이다.

복잡도 및 특징

• 시간 복잡도: $O(N+K)$ (단, $N$은 데이터의 개수, $K$는 데이터 중 최댓값)

• 공간 복잡도: $O(N+K)$ (결과 배열과 Count 배열이 필요함)

• 장점

  • 데이터의 범위($K$)가 작을 때 성능이 압도적으로 빠르다.

• 단점

  • 데이터가 아무리 적어도 최댓값($K$)이 비정상적으로 크면 메모리 낭비가 매우 심해진다. (예: 데이터가 [1, 2, 1000000] 3개뿐이어도 크기 1,000,001짜리 배열을 선언해야 한다.)
  • 음수가 포함되어 있거나 소수점 데이터의 경우 인덱스 매핑이 까다로워 정수 형태의 데이터에 적합하다.

3. Radix Sort

• 여러 자릿수를 가진 숫자나 문자열을 정렬할 때 사용한다.

1. 최하위 자릿수 (LSD; Least Significant Digit)
   • 가장 낮은 자리수부터 높은 자리수 순으로 안정 정렬을 적용한다.
2. 최상위 자릿수 (MSD; Most Significant Digit)
   • 가장 높은 자리수부터 낮은 자리수 순으로

RadixSort(A, d) {
	for (i = 1 to d) {
		StableSort(A) on digit i
	}
}

• 각 자릿수에 대해 Counting Sort를 안정 정렬로 사용하면

  • 한 패스: $O(n+k)$
  • $d$ 자릿수 전체: $O(d(n+k))$
  • $d$가 상수이고 $k=O(n)$이면 $O(n)$

• 장점

  • 빠르다.
  • 점근적으로 선형이다.
  • 코딩이 단순하다.

동작 방식 (LSD 기준, 10진수 가정)

1. 기본 정렬 기준 준비
   • 0부터 9까지의 버킷(Bucket) 또는 큐(Queue) 10개를 준비한다.
2. 낮은 자릿수부터 정렬
   • 먼저 모든 데이터의 일의 자리 숫자만 보고 해당하는 버킷에 차례대로 넣는다.
   • 버킷에서 데이터를 0번부터 9번까지 순서대로 꺼내어 원래 배열을 갱신한다. (안정 정렬 상태 유지)
3. 자릿수 높이기
   • 다음으로 십의 자리 숫자만 보고 똑같이 버킷에 넣었다가 순서대로 꺼낸다.
4. 반복
   • 데이터 중 가장 큰 숫자의 자릿수(예: 100의 자리면 3번 반복)만큼 이 과정을 반복한다.

이때 자릿수 정렬 단계에서 흔히 계수 정렬(Counting Sort)이 서브루틴으로 사용된다. 자릿수의 범위는 0~9(또는 문자의 경우 알파벳 범위)로 매우 제한적이기 때문에 계수 정렬을 효율적으로 활용할 수 있다.

복잡도 및 특징

• 시간 복잡도: $O(d\times (N+K))$

  • (단, $d$는 가장 큰 데이터의 자릿수, $K$는 기수(Radix, 10진수면 10))
  • 자릿수 $d$가 데이터 개수 $N$보다 훨씬 작다면 사실상 $O(N)$에 수렴한다.

• 공간 복잡도: $O(N+K)$

• 장점

  • 값의 범위가 넓어도 메모리 낭비가 크지 않으며, 안정 정렬이 유지된다.

• 단점

  • 한정된 키 타입(동일 길이 숫자, 단순 문자 등)에만 적용 가능하다. 부동 소수점(실수)이나 구조체처럼 자릿수를 명확히 나눌 수 없는 데이터는 정렬하기 어렵다.
  • 중간 단계에서 버킷 등의 추가적인 메모리 공간이 필요하다. (비제자리 정렬)
  • 자릿수가 너무 크다면 오히려 $O(N\log N)$ 정렬보다 비효율적일 수 있다.

4. Medians and Order Statistics (순위 통계)

• i번째 순위 통계량: n개 원소 중 i번째로 작은 원소

  • 최솟값 = 1번째 순위 통계량
  • 최댓값 = n번째 순위 통계량
  • 중앙값 = n/2번째 순위 통계량 (n이 짝수면 lower/upper median)

• 정렬 후 찾으면 O(n lg n)이지만, 모든 원소를 정렬할 필요는 없다.

4.1. Min/Max 동시에 찾기

• 원소를 쌍으로 묶어 처리하면 3 비교 / 2 원소 = O(3n/2)로 가능

4.2. Randomized Selection

• Quicksort의 partition을 활용하되, 한쪽 부분 배열만 재귀 탐색
  • 최악: T(n) = T(n-1) + O(n) = O(n²)
  • 최선/평균: T(n) = T(9n/10) + O(n) = O(n)
  • 기대 시간: O(n) (지시 확률 변수와 치환법으로 증명)

4.3. Worst-Case Linear Time Selection (Median of Medians)

• 이론적 관심의 알고리즘으로 최악의 경우에도 O(n) 보장

  1. n개 원소를 5개씩 그룹으로 나눔
  2. 각 그룹의 중앙값을 구함
  3. ⌊n/5⌋개 중앙값들의 중앙값 x를 재귀적으로 찾음
  4. x를 기준으로 partition (rank k 결정)
  5. i = k면 반환, i < k면 왼쪽 재귀, i > k면 오른쪽 재귀

• 핵심 분석

  • 좋은 피벗 x보다 큰(작은) 원소가 최소 3n/10 - 6개 존재하므로, 재귀 호출은 최대 7n/10 + 6개 원소에 대해서만 발생

• 점화식

  • $T(n)\le T(\lceil n/5\rceil )+T(7n/10+6)+O(n)$
  • → $T(n)=O(n)$

• 치환법으로 증명

  • 1/5 + 7/10 = 9/10 < 1 이라는 점이 핵심이며,
  • 이 때문에 그룹 크기를 5로 잡는다.