Sorting Quicksort Quicksort:Time Complexity Q:What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 if p<r 2 q PARTITION(A,p.r) 3 QUICKSORT(A,p.q-1) 4 QUICKSORT(A,q +1,r) 口+4y，艺2QC￥ Ma Jun (Institute of Computer Software) Problem Solving April 19.2022 4/42
Sorting Quicksort Quicksort: Time Complexity Q : 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 19, 2022 4 / 42
Sorting Quicksort Quicksort:Time Complexity Q:What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 if p<r 2 q PARTITION(A.p.r) 3 QUICKSORT(A,p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(n1)+T(n2)+cn where: 4口4的在是安QC Ma Jun (Institute of Computer Software) Problem Solving April 19.2022 4/42
Sorting Quicksort Quicksort: Time Complexity Q : 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 19, 2022 4 / 42
Sorting Quicksort Quicksort:Time Complexity Q:What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 if p<r 2 q =PARTITION(A.p.r) 3 QUICKSORT(A,p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(n1)+T(n2)+cn where: 1=q-1-p+1=q-p n2=r-(q+1)+1=T-q n1 +n2=r-p initially,p=1,r =n 口卡4心，2生Q0 Ma Jun (Institute of Computer Software) Problem Solving April 19.2022 4/42
Sorting Quicksort Quicksort: Time Complexity Q : 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 19, 2022 4 / 42
Sorting Quicksort Quicksort:Time Complexity Q:What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 if p<r 2 q =PARTITION(A.p.r) 3 QUICKSORT(A,p.q-1) 4 QUICKSORT(A.q+1,r) The recurrence:T(n)=T(n1)+T(n2)+cn where: 1=q-1-p+1=q-p n2=r-(q+1)+1=T-q n1+n2=r-p initially,p=1,r =n n1,n2 vary and depend on q PARTITION(A,p,r) 口+4y，法·2QC￥ Ma Jun (Institute of Computer Software) Problem Solving April 19.2022 4/42
Sorting Quicksort Quicksort: Time Complexity Q : 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 19, 2022 4 / 42
Sorting Quicksort Quicksort:Time Complexity Q:Which factor would affect the efficiency of QUICKSORT? always produces a 9-to-1 split cn 品n cn logion ” 品n 品n 品n cn 0g10/9T To0 品n aa4a4n4, cn nn≤C刀 w≤C刀 發 O(n Ign) 0a0
Sorting Quicksort Quicksort: Time Complexity Q : 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 19, 2022 5 / 42