南京大学：《计算机问题求解》课程教学资源（课件讲稿）排序与选择 sorting and selection

Problem Solving 2-9 Sorting and Selection Ma Jun Institute of Computer Software April 19,2022 +口，4y，4三，4=，三0QC

Problem Solving 2-9 Sorting and Selection Ma Jun Institute of Computer Software April 19, 2022

Contents ① Sorting ② Selection +口，4y，4三4兰，左0QC

Contents 1 Sorting 2 Selection

Contents ①Sorting ●Quicksort o Randomized Quicksort oComparison-based Sort Sorting in Linear Time ②Selection o Minimum and Maximum o 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 Q:What is the KEY idea of Quicksort? 酸 ，口+4y,。法，生，生QG

Sorting Quicksort Quicksort Q : 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 19, 2022 1 / 42

Sorting Quicksort Quicksort Q:What is the KEY idea of Quicksort? pivot 0000可60000000 酸 ，口+4y,。法，生，生QG

Sorting Quicksort Quicksort Q : 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 19, 2022 1 / 42

Sorting Quicksort Quicksort Q:What is the KEY idea of Quicksort? pivot 0000可60000000 for any element in this segment,the key is not greater small than pivot. 發 4口4的，，左·生生 3Q0

Sorting Quicksort Quicksort Q : 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 19, 2022 1 / 42

Sorting Quicksort Quicksort Q:What is the KEY idea of Quicksort? pivot 0000a6000000可 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

Sorting Quicksort Quicksort Q : 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 19, 2022 1 / 42

Sorting Quicksort Quicksort Q:What is the KEY idea of Quicksort? pivot 0000O6o0o0000 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 口卡4的，·左·进，2Q0 Ma Jun (Institute of Computer Software) Problem Solving April 19.2022 1/42

Sorting Quicksort Quicksort Q : 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 19, 2022 1 / 42

Sorting Quicksort Quicksort Q: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) 美 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 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. 美 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