Sorting in Linear Time

Decision tree (결정트리)

• 결정트리는 얼마나 많은 leaves를 가지나?
  n개의 원소개 있다면 최소 n!개를 가진다.
  
  
  결정트리
  
  

• root부터 leaves까지의 가장 길이는?
  알고리즘에 따라 다르다.

  • 삽입 정렬 - (n²)
  • 합병 정렬 - (n lg n)

• n개의 요소를 정렬하는 의사 결정 트리는 높이 Ω(n lg n)이다.

  
  

Counting sort (계수정렬)

• 계수 정렬은 비교 정렬이 아니다.

1. (a) 입력한 숫자를 A에 넣는다. C에는 입력된 숫자들의 개수를 넣는다.
2. (b) C에서 앞에 칸의 숫자를 뒤에 칸의 숫자에 더한다.
3. (c) A의 마지막 칸 부터 시작해 첫 번째 칸까지 C를 참고해 B에 숫자를 넣는다. 예를 들어 A의 마지막 칸의 숫자 3을 통해 C의 3번의 숫자로 가서 3번 숫자가 7임을 이용한다.
   B의 7번에 3을 집어 넣으면 된다. 그리고 C의 3번 7은 1을 빼서 6으로 바꾼다. 이런 식으로 반복하면 (f)처럼 정렬이 완성된다.