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

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

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 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 MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 3/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

Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 PARTITION(A,p.r) 3 QUICKSORT(A.p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(m)+T(n2)+cn where: m=9-1-p+1=q-p 2=r-(q+1)+1=r-q m+n2=r-p initially,p=1,r =n m,n2 vary and depend on q=PARTITION(A,p,r) MA Jun (Institute of Computer Software) Problem Solving Api23.2020 4/40

Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40

Sorting Quicksort Quicksort:Time Complexity Question:Which factor would affect the efficiency of QUICKSORT? always produces a 9-to-1 split cn 品n cn logion 品n 品n cn 0g10/9T 8品n 恐n 4aa444, cn ≤C刀 the choice of Pivot would affect the tree height. w≤C刀 O(n Ign) MA Jun (Institute of Computer Software) Problem Solving Aprl23.2020 5/40

Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? always produces a 9-to-1 split the choice of Pivot would affect the tree height. MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 5 / 40

Sorting Quicksort Quicksort:Time Complexity Question:Which factor would affect the efficiency of QUICKSORT? always produces a 9-to-1 split cn 9 cn logion 品n 品n cn 0g10/9 Too 11 cn / any split of constant proportionality ≤CI o tree height:(Ig n) o cost of each level:cn u≤Cn o total running time: O(nlgn) O(n Ign) MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 6/40

Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? always produces a 9-to-1 split any split of constant proportionality tree height: Θ(lg n) cost of each level: cn total running time: O(n lg n) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 6 / 40

Sorting Quicksort Quicksort:Time Complexity Question Which factor would affect the efficiency of QUICKSORT? cn 品n cn 10g10刀 品n n号目力： cn /N 0g10/97 品n 729 10o0H cn any split of9Npfr州 nn…≤C刀 What is the WORST CASE? uu≤C刀 T(n)=maxosqsn-1(T(q)+T(n-q-1))+e(n) O(nlgn) MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 7/40

Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? any split of ///////////////////////////// constant proportionality What is the WORST CASE? T(n) = max0≤q≤n−1(T(q) + T(n − q − 1)) + Θ(n) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 7 / 40