Sorting Quicksort Quicksort Question:What are the SIMILARITIES and DIFFERENCES between Quicksort and Mergesort? QUICKSORT(A,p,r) MERGE-SORT(A,p,r) 1 if p<r 1 ifp<r 2 g 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 MA Jun (Institute of Computer Software) Problem Solving Apil23.20202/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort Question : 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 23, 2020 2 / 40
Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? I unrestricted PARTITION(A,p.r) 1 x=A(r] 2i=p-1 3 for j=ptor-1 4 ifA[U]≤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口45，，左·生空
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Partition k Question : 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 23, 2020 3 / 40
Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? ≤x I unrestricted PARTITION(A,p.r) 1 x =Alr] 2 0=p-1 3 for j p tor-1 4 ifA[U]≤x i=i+1 6 exchange A[i]with A[j] 7 exchange A[i +1]with A[r] 8 return i+1 4口45，，左·生空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Partition k Question : 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 23, 2020 3 / 40
Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? ≤x unrestricted PARTITION(A,p.r) 1 x A[r] 2 0=p-1 for=p tor-1 4 tA[U]≤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步，，左·生，空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Partition k Question : 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 23, 2020 3 / 40
Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? ≤x 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 0=p-1 index k,we have: 3 for j=p tor- 4 fA[U]≤x L.Ifp≤k≤i,then A[k≤x. 5 i=i+1 2.Ifi+1≤k≤j-l,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 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving Apil23.20203/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort: Partition k Question : 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 23, 2020 3 / 40