2017/1/29

[S9S99]

진행 상황

• p.354 ~ p.361

  내용 정리

• Removing Recursion
  • 지난 시간 만들었던 큇소트에서 재귀적 호출을 재거해서 속도를 높힘
• Efficiency of Quicksort
  • 일반적으로 O (N * logN)
• Radix Sort
  • 인덱스 숫자로 분해해서 정렬(1, 10, 100 자리 각각의 숫자로 정렬 하는 형태). 비교를 하지 않고 정렬
  • 1의 자리 숫자만으로 0~9 순서대로 정렬 -> 10의 자리 -> ... 정렬 완료 의 흐름
• Efficiency of the Radix Sort
  • O(N)
  • 항목이 많으면 긴 키가 필요해서 O(N*logN)
  • 비교는 없지만 복사가 더 많이 발생하기 때문에 quicksort 보다 약 두배 많은 메모리가 필요