Problem Solving 2-9 Sorting and Selection MA Jun Institute of Computer Software April 23,2020
Problem Solving 2-9 Sorting and Selection MA Jun Institute of Computer Software April 23, 2020
Contents ① Sorting ② Selection
Contents 1 Sorting 2 Selection
Contents ①Sorting Quicksort o Randomized Quicksort Comparison-based Sort Sorting in Linear Time ②Selection ●Minimum and Maximum Selection in Expected Linear Time o Selection in Worst-case Linear Time
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? pivot 0000O6o000000 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 MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 1/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 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 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