Sorting Quicksort Quicksort Q:What are the SIMILARITIES and DIFFERENCES between Quicksort and Mergesort? QUICKSORT(A.p.r) MERGE-SORT(A,p,r) 1 ifp<r 1 ifp<r 2 q=PARTITION(A,p,r) 2 9=Lp+r)/2 3 QUICKSORT(A,p.q-1) 3 MERGE-SORT(A,p,q) 4 QUICKSORT(A.q +1,r) 4 MERGE-SORT(A,q+1,r) 5 MERGE(A,p,q,r) Similarity:both are divide-and-conquer strategies. Difference:the process QuickSort MergeSort Partition hard easy Combination easy hard -40w Ma Jun (Institute of Computer Software) Problem Solving April 19.2022 2/42
Sorting Quicksort Quicksort Q : What are the SIMILARITIES and DIFFERENCES between Quicksort and Mergesort? VS Similarity: both are divide-and-conquer strategies. Difference: the process QuickSort MergeSort Partition hard easy Combination easy hard Ma Jun (Institute of Computer Software) Problem Solving April 19, 2022 2 / 42
Sorting Quicksort Quicksort:PARTITION Q:How to prove the correctness of PARTITION? ≤x unrestricted PARTITION(A,p.r) 1 x=A[r] 2i=p-1 3 for j=p tor-1 4 ifA[]≤x 5 i=i+1 6 exchange A[i]with A[j] 7 exchange A[i +1]with A[r] 8 return i+1 4口4的，，左+生，2Q0
Sorting Quicksort Quicksort: Partition k Q : How to prove the correctness of Partition? At the beginning of each iteration of the loop of lines 3-6, for any array index k, we have: Ma Jun (Institute of Computer Software) Problem Solving April 19, 2022 3 / 42
Sorting Quicksort Quicksort:PARTITION Q:How to prove the correctness of PARTITION? ≤x unrestricted PARTITION(A,p.r) 1 x=A[r] 2 园=p-1 3 for j=p tor-1 4 ifA[]≤x 5 i=i+1 6 exchange A[i]with A[j] 7 exchange A[i +1]with A[r] ，口+4y，。左，，生QG
Sorting Quicksort Quicksort: Partition k Q : How to prove the correctness of Partition? At the beginning of each iteration of the loop of lines 3-6, for any array index k, we have: Ma Jun (Institute of Computer Software) Problem Solving April 19, 2022 3 / 42
Sorting Quicksort Quicksort:PARTITION Q:How to prove the correctness of PARTITION? >X unrestricted PARTITION(A.P.r) 1 x = A[r] 2 园=p-1 3 for=p tor-1 4 fA[]≤x 5 i=i+1 6 exchange A[i]with A[j] 7 exchange A[i +1]with A[r] 8 return i+1 ，口+4的，。之，生，生 0Q0
Sorting Quicksort Quicksort: Partition k Q : How to prove the correctness of Partition? At the beginning of each iteration of the loop of lines 3-6, for any array index k, we have: Ma Jun (Institute of Computer Software) Problem Solving April 19, 2022 3 / 42
Sorting Quicksort Quicksort:PARTITION Q:How to prove the correctness of PARTITION? ≤x I unrestricted PARTITION(A.P.r) At the beginning of each iteration of 1 x= A[r] the loop of lines 3-6,for any array 2 =p-1 index k,we have: 3 for j=p tor-1 4 fA[]≤x L.Ifp≤k≤i,then A[k≤x. 5 i=i+1 2.Ifi+1≤k≤j-1,then A[k]>x. 6 exchange A[i]with A[j] 3.If k =r,then A[k]=x. 7 exchange A+I]with Ar] 8 return i+1 發 4口卡4心·左，进，空Q0 Ma Jun (Institute of Computer Software) Problem Solving Apr19.2022 3/42
Sorting Quicksort Quicksort: Partition k Q : How to prove the correctness of Partition? At the beginning of each iteration of the loop of lines 3-6, for any array index k, we have: Ma Jun (Institute of Computer Software) Problem Solving April 19, 2022 3 / 42