Sorting in Linear Time

---

01. Comparison Sorts의 한계

• 지금까지 본 정렬은 비교 기반 정렬이었음 -> 이러한 정렬 알고리즘은 결정 트리(Decision Tree)로 추상화 시켜서 모델링할 수 있음

★ n개의 요소를 비교 기반 정렬할 때 최소한 n!개의 leaf node가 나옴 = 알고리즘 비교 횟수
알고리즘이 수행하는 비교 횟수 = 결정 트리의 높이 = 트리의 높이는 리프 노드 개수에 따라 결정

 
 

- Lower Bound for Sorting: Ω(n lg n)

• 결정 트리의 높이는 Ω(n lg n)이라는 한계 정리

 
 
 

---

02. Count sort(계수 정렬)

• Counting Sort는 비교 기반이 아닌 정렬 알고리즘으로, 정렬할 입력이 특정 k범위 내의 정수일 때 선형 시간에 동작함
• 요소들의 빈도를 세는 배열을 만들어 각 요소의 위치를 결정함
• Counting Sort의 시간 복잡도는 O(n+k)
  • n은 입력 크기, k는 입력값의 범위로써, 입력의 개수와 범위 둘 다 영향 받는다는 뜻
  • 만약 k=O(n)이면, 시간 복잡도는 O(n)으로 선형 시간에 동작할 수 있음
  • k > n이면 유용한 알고리즘 됨, k < n이면 비효율적인 알고리즘 됨
• 안정적(Stable)이지만, 추가적인 B, C 메모리 공간이 필요하므로 non In-place

 
 
 
 

---

03. Radix sort (기수 정렬)

• Radix Sort는 여러 자릿수로 이루어진 숫자를 자릿수 별로 처리하여 정렬하는 알고리즘(IP, 전번같이 고정된 길이일 때만 유용한 정렬)
• LSD (Least Significant Digit)부터 시작하여 각 자릿수를 정렬하며, 안정적인 정렬 알고리즘(예: Counting Sort)을 이용해 자릿수 별로 처리함
• Radix Sort의 시간 복잡도는 O(d⋅(n+k))
  • d는 자릿수의 개수, k는 자릿수의 가능한 값의 범위
  • 만약 k=O(n)이면, 시간 복잡도는 O(d⋅n)이 되어 선형 시간에 동작할 수 있음

 
 
 

---

04. Bucket Sort (버켓 정렬)

• Bucket Sort는 입력 값들이 균등한 분포를 따른다는 가정 하에 동작하는 알고리즘
• 입력 값을 여러 개의 버킷에 나누어 각 버킷을 개별적으로 정렬한 후, 버킷의 순서대로 합침
• 각 버킷의 요소가 거의 균등하게 분포될 경우, 각 버킷을 정렬하는 데 드는 시간이 상수에 가까워지고, 총 시간 복잡도는 O(n)이 됨 → 하지만 버킷에 요소가 불균등하게 몰리면, 시간 복잡도가 더 높아질 수 있음
• 그냥 삽입 정렬 등으로 각각 처리함 → 한 버켓에 1~2개 정도만 있으니까 삽입 정렬이어도 하나당 O(1)이 걸림 → 그걸 n개 버켓 처리하니까 O(n)이 됨