Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 q PARTITION(A,p.r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A.q+1,r) @ 4口卡4①1注·是生Q MA Jun (Institute of Computer Software) Problem Solving Ap23.20204/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40
Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 q PARTITION(A,p.r) 3 QUICKSORT(A.p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(m)+T(n2)+cn where: 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving April23.20204/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40
Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 PARTITION(A,p.r) 3 QUICKSORT(A.p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(m)+T(n2)+cn where: m=9-1-p+1=q-p 2=r-(q+1)+1=r-q n1十2=r-p initially,p=1,r =n 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving Ap23.20204/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40
Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 PARTITION(A,p.r) 3 QUICKSORT(A.p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(m)+T(n2)+cn where: m=9-1-p+1=q-p 2=r-(q+1)+1=r-q m+n2=r-p initially,p=1,r =n m,n2 vary and depend on q PARTITION(A,p,r) 口卡0，法是，生QC MA Jun (Institute of Computer Software) Problem Solving Ap23.20204/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40
Sorting Quicksort Quicksort:Time Complexity Question:Which factor would affect the efficiency of QUICKSORT? always produces a 9-to-1 split cn 品n cn logion ” 品n 品n 品n cn 品n 品n 4aa44, cn nn≤C刀 w≤C刀 O(n Ign) 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? always produces a 9-to-1 split the choice of Pivot would affect the tree height. MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 5 / 40