Problem Solving 2-9 Sorting and Selection MA Jun Institute of Computer Software April 23,2020 +口+4y，4三，4=，三0QC
Problem Solving 2-9 Sorting and Selection MA Jun Institute of Computer Software April 23, 2020 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Contents ① Sorting ② Selection +口+4y，4三4兰，左0QC
Contents 1 Sorting 2 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Contents ①Sorting Quicksort o Randomized Quicksort o Comparison-based Sort Sorting in Linear Time ②Selection ●Minimum and Maximum Selection in Expected Linear Time o Selection in Worst-case Linear Time +口+4y，4三，4=，三0QC
Contents 1 Sorting Quicksort Randomized Quicksort Comparison-based Sort Sorting in Linear Time 2 Selection Minimum and Maximum Selection in Expected Linear Time Selection in Worst-case Linear Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sorting Quicksort Quicksort Question What is the KEY idea of Quicksort? ，口+4y，。法，，生)QG
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort Question : What is the KEY idea of Quicksort? pivot small for any element in this segment, the key is not greater than pivot. large for any element in this segment, the key is greater than pivot. To Be Sorted Recursively MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 1 / 40
Sorting Quicksort Quicksort Question What is the KEY idea of Quicksort? pivot 0000a60000000 题 4口4步，，左·生，空 2ao
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort Question : What is the KEY idea of Quicksort? pivot small for any element in this segment, the key is not greater than pivot. large for any element in this segment, the key is greater than pivot. To Be Sorted Recursively MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 1 / 40
Sorting Quicksort Quicksort Question What is the KEY idea of Quicksort? pivot 0000O60000000 for any element in this segment,the key is not greater small than pivot. 题 4口45，，左·生空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort Question : What is the KEY idea of Quicksort? pivot small for any element in this segment, the key is not greater than pivot. large for any element in this segment, the key is greater than pivot. To Be Sorted Recursively MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 1 / 40
Sorting Quicksort Quicksort Question What is the KEY idea of Quicksort? pivot 0000O6000o000 for any element in for any element in this segment,the this segment,the key is not greater small large key is greater than than pivot. pivot. 口+4步，。左，生生 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort Question : What is the KEY idea of Quicksort? pivot small for any element in this segment, the key is not greater than pivot. large for any element in this segment, the key is greater than pivot. To Be Sorted Recursively MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 1 / 40
Sorting Quicksort Quicksort Question What is the KEY idea of Quicksort? pivot 0000O6o00o000 for any element in for any element in this segment,the this segment,the key is not greater small large key is greater than than pivot. pivot. To Be Sorted Recursively 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving Ap23.20201/40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting Quicksort Quicksort Question : What is the KEY idea of Quicksort? pivot small for any element in this segment, the key is not greater than pivot. large for any element in this segment, the key is greater than pivot. To Be Sorted Recursively MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 1 / 40
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 q PARTITION(A,p,r) 2 9=L(p+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) 美 4 MA Jun (Institute of Computer Software) Problem Solving Ap23.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 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 q PARTITION(A,p,r) 2 9=L(p+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. 40￥ MA Jun (Institute of Computer Software) Problem Solving Apl23.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
