2017/1/27

[S9S99]

진행 상황

• p.333 ~ p.344

  내용 정리

• Quicksort
  • 평균 O(N*logN) 최악 O(N^2)
  • 리스트에서 항목 하나를 선택(피벗이라고 부름)해서 피벗을 기준으로 작은 값이 앞에 오고 큰값을 뒤로 가도록 분할 -> 피벗은 이동하지 않고 두개의 리스트를 재귀적으로 반복
  • 알고리즘의 효율을 높히기 위해서 피벗을 선택하는 방법이 중요