[알고리즘] 분할정복 - Quicksort(빠른정렬)

💡빠른정렬 

 - 기준점(pivot)을 기준으로 배열을 둘로 쪼갠다

 - 기준점보다 작으면 왼쪽, 크면 오른쪽으로 분리

 - 다시 왼쪽, 오른쪽 배열에서 기준점을 잡고 분리

 - 배열에서 기준점을 제외하고 모든 원소와 비교하므로 점화식은 T(n) = n-1 그 외 정렬이나 합병 과정은 없음

 - 일정 복잡도 계산 X

 

quickwort(){}

partition(){}

 

✔️ 최악의 시간복잡도

 - 이미 오름차순으로 정렬되어 있어 왼쪽 배열은 아무것도 없고 오른쪽에는 정렬된 배열이 남아 무의미하게 계속 기준을 잡고 비교하는 과정을 거치기 때문

 - 

T(n) = T(0) + T(n-1) + n -1 , if n>0

(* n개의 배열을 비교하면서 n-1 비교, 왼쪽은 0, 오른쪽은 다시 n-1개의 배열로 이뤄짐)

      = n(n-1)/2

 

귀납적 증명

 

✔️ 평균 시간복잡도