카운팅 정렬(Counting Sort), 기수 정렬(Radix Sort)

1. 비교 모델에서의 정렬

1) 비교모델이란?

• 데이터 항목 간의 비교 연산만을 이용해 정렬을 수행하는 방식
• 병합, 퀵, 힙 등 전통적인 정렬 알고리즘이 비교모델에 속함

 

 

2) 비교모델의 탐색과 정렬의 하한

탐색 하한

• 탐색의 경우 최악의 경우 $\log n$번의 비교가 필요함
• 이유
  • 탐색 알고리즘은 이진 결정 트리(Binary Decision Tree)로 표현할 수 있음
    • 결정 트리의 각 내부 노드는 항목 간의 비교를 나타내며, 루트에서 리프까지의 경로는 탐색 과정임
  • 탐색 가능한 n개의 항목을 모두 포함하려면 트리의 최소 깊이는 $\log n$이 됨

 

정렬 하한

• 정렬 문제는 최소 $n \log n$번의 비교가 필요함
• 증명
  1. 정렬된 배열의 경우의 수(모든 가능한 결과)는 $n!$(순열의 개수)임
  2. n!개의 리프를 포함하는 결정 트리의 최소 깊이는 $\log(n!)$임
     • 높이가 $h$인 이진 트리는 최대 $2^h$개의 리프를 가질 수 있음
     • 따라서, $2^h \geq n!$ 이여야 n!개의 결과를 모두 표현할 수 있음
     • 이 식을 로그로 변환하면: $h ≥ \log_{2} (n!)$
  3. $\log (n!)$을 스털링 근사를 통해 계산하면 $n \log n - n$이 되며, 이는 $O(n \log n)$임

 

비교모델의 한계

• 비교 모델 정렬은 $O(n \log n)$ 시간은 피할 수 없는 한계임
• 병합 정렬과 퀵 정렬 같은 알고리즘은 이 한계에 도달하며 최적의 성능을 제공함

 

 

 

2. RAM 모델에서의 정렬

1) RAM 모델이란?

• RAM(Random Access Machine) 모델에서는 정수형 데이터라는 가정을 활용함
• 비교 연산 대신 정수 정렬 특성을 활용하여 정렬을 수행함으로써 비교 정렬 보다 더 빠르게 정렬할 수 있음
  • 정수 정렬 특성
    • 정수 데이터를 다룸
      • 정렬 대상은 모두 정수로 표현된 데이터임
    • 정수의 범위를 활용
      • 정렬할 정수 값은 $0$부터 $k−1$까지의 범위에 속함
      • $k$는 정수 값의 최대 범위를 나타탬
    • RAM 모델 기반의 효율성
      • 정수 값이 RAM 모델의 워드 크기(예: 32비트, 64비트)에 맞는다고 가정함
      • 워드 크기에 맞으면, 정수의 비교나 산술 연산을 상수 시간($O(1)$)에 수행할 수 있음
    • 정수 정렬의 대표적인 알고리즘
      • 카운팅 정렬
      • 기수 정렬

 

 

2) 카운팅 정렬 (Counting Sort)

카운팅 정렬이란?

• 입력 배열에서 항목의 빈도를 계산한 뒤, 이를 이용해 정렬된 결과를 생성하는 알고리즘

 

알고리즘

1. 정수의 범위를 기준으로 배열 생성
   • 크기가 $k$인 배열 count를 생성함
   • 여기서 $k$는 입력 배열 정수값의 최대 범위
2. 빈도 계산
   • 입력 배열을 순회하며 각 정수의 빈도를 count에 저장
3. 누적 빈도 계산
   • count[i]에 count[i - 1]을 더하여 누적 빈도를 계산함
   • 이를 통해 각 정수의 최종 위치를 결정함
4. 정렬된 배열 생성
   • 입력 배열을 다시 순회하면서, 각 항목을 누적 빈도를 기반으로 올바른 위치에 삽입함

 

예제

• 입력 배열: A = [3, 1, 2, 2, 4, 5]
  • $k = 8$ (0 ≤ 키 < 6)
• 단계
  1. 정수의 범위를 기준으로 배열 생성
     • C = [0, 0, 0, 0, 0, 0]
  2. 빈도 계산
     • C = [0, 1, 2, 1, 1, 1]
  3. 누적 빈도 계산
     • C = [0, 1, 3, 4, 5, 6]
  4. 누적 빈도로 위치 계산
     • 역순으로 A를 순회하며 C를 참조
       • $A[0] = 3 → C[3] = 4 → B[4 - 1] = 3 → C[3]--$
       • $A[1] = 1 → C[1] = 1 → B[1 - 1] = 1 → C[1]--$
       • $A[2] = 2 → C[2] = 3 → B[3 - 1] = 2 → C[2]--$
       • $A[3] = 2 → C[2] = 2 → B[2 - 1] = 2 → C[2]--$
       • $A[4] = 4 → C[4] = 5 → B[5 - 1] = 4 → C[4]--$
       • $A[5] = 5 → C[5] = 6 → B[6 - 1] = 5 → C[5]--$
  5. 결과: B = [1, 2, 2, 3, 4, 5]

 

시간 복잡도

• 빈도 계산: $O(n)$
• 누적 빈도 계산: $O(k)$
• 정렬된 배열 생성: $O(n)$
• ⇒ 총 시간 복잡도: $O(n + k)$

 

장점과 단점

• 장점
  • 비교를 사용하지 않으므로 $O(n \log n)$ 한계를 극복
  • 데이터의 크기 $k$가 작고 입력 크기 $n$이 클 때 효율적
• 단점
  • $k$가 $n$보다 훨씬 클 경우(예: $n = 10$, $k = 10^6$), 공간과 시간이 비효율적
  • 정수형 데이터에만 사용 가능

 

 

3) 기수 정렬 (Radix Sort)

기수 정렬이란?

• 정수를 자리수 단위로 분리하여 각 자리수를 기준으로 정렬하는 알고리즘
• 각 단계에서 카운팅 정렬을 사용해 정렬을 수행함

 

알고리즘

1. 자리수 분리
   • 정수를 특정 진법(예: 10진수, 2진수)로 표현함
2. 낮은 자리수부터 높은 자리수 순으로 정렬
   • 각 자리수(1의 자리, 10의 자리, …)를 분리하여 정렬함
   • 정렬 과정은 안정 정렬(Stable Sort)을 사용하여 순서를 유지함

 

예제

• 입력 배열: [329,457,657,839,436,720,355]
• 과정
  1. 1의 자리수 기준 정렬
     • 정렬 기준: [329,457,657,839,436,720,355]
     • 1의 자리: [9,7,7,9,6,0,5]
     • 정렬 결과: [720,329,839,457,657,355,436]
  2. 10의 자리수 기준 정렬
     • 정렬 기준: [720,329,839,457,657,355,436]
     • 10의 자리: [2,2,3,5,5,5,3]
     • 정렬 결과: [329,355,436,457,657,720,839]
  3. 100의 자리수 기준 정렬
     • 정렬 기준: [329,355,436,457,657,720,839]
     • 100의 자리: [3,3,4,4,6,7,8]
     • 정렬 결과: [329,355,436,457,657,720,839]
• 결과: [329,355,436,457,657,720,839]

 

시간 복잡도

• 각 자리수에 대한 정렬: $O(n + b)$
  • $b$: 기수(진법)
• 자리수 개수 $d$: $O(log_{b} k)$
• ⇒ 총 시간 복잡도: $O((n + b)\times d)$

 

장점과 단점

• 장점
  • $k$가 매우 커도 $n$과의 비율에 따라 효율적
  • $b = n$으로 설정하면 $O(n)$에 가까운 성능 달성 가능
  • 안정 정렬로, 기존 순서를 유지하며 정렬
• 단점
  • 데이터가 정수 형태여야 함
  • 자리수 기준으로 정렬하기 때문에 실수 데이터를 다루기 어렵다