上海交通大学：《C程序与算法设计》课程教学资源（课件讲稿）Lecture 02 Divide and Conquer

上浒充通大学 SHANGHAI JLAO TONG UNIVERSITY Computer Algorithm Design and Analysis Lecture 2/Week 12:Divide and Conquer Yongxin ZHU,Weiguang SHENG 强 具是 3合 SHANG 1日G

Computer Algorithm Design and Analysis Lecture 2/ Week 12: Divide and Conquer Yongxin ZHU, Weiguang SHENG

上游充通大粤 Recursive algorithms SHANGHAI JIAO TONG UNIVERSITY General idea: Divide a large problem into smaller ones ·By a constant ratio By a constant or some variable Solve each smaller one recursively or explicitly Combine the solutions of smaller ones to form a solution for the original problem Divide and Conquer 3/12/2022 2

3/12/2022 2 Recursive algorithms General idea: • Divide a large problem into smaller ones • By a constant ratio • By a constant or some variable • Solve each smaller one recursively or explicitly • Combine the solutions of smaller ones to form a solution for the original problem Divide and Conquer

上浒充通大学 Divide-and-Conquer SHANGHAI JIAO TONG UNIVERSITY Divide-and-conquer. Break up problem into several parts. e Solve each part recursively. Combine solutions to sub-problems into overall solution. Most common usage. Break up problem of size n into two equal parts of size vn. Solve two parts recursively. Combine two solutions into overall solution in linear time. ©Consequence. ·Brute force:n2. Divide et impera. Veni,vidi,vici. Divide-and-conquer:n log n. Julius Caesar

3 Divide-and-Conquer Divide-and-conquer. • Break up problem into several parts. • Solve each part recursively. • Combine solutions to sub-problems into overall solution. Most common usage. • Break up problem of size n into two equal parts of size ½n. • Solve two parts recursively. • Combine two solutions into overall solution in linear time. Consequence. • Brute force: n2. • Divide-and-conquer: n log n. Divide et impera. Veni, vidi, vici. - Julius Caesar

上游充通大学 SHANGHAI JLAO TONG UNIVERSITY Divide and Conquer Example1:Merge Sort 强 LAMAANAMA A学 SHANG 1日G

Divide and Conquer Example1: Merge Sort

上游充通大学 Sorting SHANGHAI JLAO TONG UNIVERSITY Sorting.Given n elements,rearrange in ascending order. Obvious sorting applications. Non-obvious sorting applications. List files in a directory. Data compression. Organize an MP3 library. Computer graphics. List names in a phone book. Interval scheduling. Display Google PageRank Computational biology. results. Minimum spanning tree. Supply chain management Problems become easier once Simulate a system of particles. sorted. Book recommendations on Find the median. Amazon. Find the closest pair. Load balancing on a parallel Binary search in a computer. database. Identify statistical outliers. Find duplicates in a mailing list

5 Obvious sorting applications. List files in a directory. Organize an MP3 library. List names in a phone book. Display Google PageRank results. Problems become easier once sorted. Find the median. Find the closest pair. Binary search in a database. Identify statistical outliers. Find duplicates in a mailing list. Non-obvious sorting applications. Data compression. Computer graphics. Interval scheduling. Computational biology. Minimum spanning tree. Supply chain management. Simulate a system of particles. Book recommendations on Amazon. Load balancing on a parallel computer. . . . Sorting Sorting. Given n elements, rearrange in ascending order

上游充通大学 Mergesort SHANGHAI JIAO TONG UNIVERSITY ©Mergesort.. Divide array into two halves. Recursively sort each half. Jon von Neumann(1945) Merge two halves to make sorted whole. A G R 工TH MS A G R divide 0(1) A G L R HI M S T sort 2T(n/2) A merge O(n)

6 Mergesort Mergesort. • Divide array into two halves. • Recursively sort each half. • Merge two halves to make sorted whole. merge sort divide A L G O R I T H M S A L G O R I T H M S A G L O R H I M S T A G H I L M O R S T Jon von Neumann (1945) O(n) 2T(n/2) O(1)

上浒充通大学 Merging SHANGHAI JIAO TONG UNIVERSITY Merging.Combine two pre-sorted lists into a sorted whole. How to merge efficiently? Linear number of comparisons. ·Use temporary array. R H工M S T A G H I Challenge for the bored.In-place merge.[Kronrud,1969] using only a constant amount of extra storage

7 Merging Merging. Combine two pre-sorted lists into a sorted whole. How to merge efficiently? • Linear number of comparisons. • Use temporary array. Challenge for the bored. In-place merge. [Kronrud, 1969] A G L O R H I M S T A G H I using only a constant amount of extra storage

上游充通大学 So Easy? SHANGHAI JIAO TONG UNIVERSITY ©合并排序 对于一个要排序的数组，把它分为两个长度大致相同的部分，并 对每个长度大于1的子数组进行递归排序，然后将这两个排好序的 数组合并就可以得到一个有序数组。合并的方法是：设置两个指 针和j,分别指向两个有序子数组的第一个元素，然后比较它们指 向的值，取其中较小者放入到结果数组中，并将相应指针后移一 个位置。重复此过程直到某个子数组的元素全部加入到结果数组 中为止。如果此时另一个数组中仍有元素，只需将剩余元素复制 到结果数组的末尾即可。吴哲辉等 《算法设计方法》 取其中较小者放入到结果数组中，并将相应指针后移一个位置？ ©找到一边的大的值后，应该移动另外一边的指针，一直移到边 界或者另外一边的值更大。 8

8 So Easy? 合并排序 对于一个要排序的数组，把它分为两个长度大致相同的部分，并 对每个长度大于1的子数组进行递归排序，然后将这两个排好序的 数组合并就可以得到一个有序数组。合并的方法是：设置两个指 针i和j，分别指向两个有序子数组的第一个元素，然后比较它们指 向的值，取其中较小者放入到结果数组中，并将相应指针后移一 个位置。重复此过程直到某个子数组的元素全部加入到结果数组 中为止。如果此时另一个数组中仍有元素，只需将剩余元素复制 到结果数组的末尾即可。 取其中较小者放入到结果数组中，并将相应指针后移一个位置? 找到一边的大的值后，应该移动另外一边的指针，一直移到边 界或者另外一边的值更大。 吴哲辉等 《算法设计方法》

上浒充通大学 Merge sort SHANGHAI JIAO TONG UNIVERSITY MERGE-SORT A[I.·n] 1.Ifn=1.done 2.Recursively sort 4[1..Tn/21] andA[「n/2+1..n]. 3.Merge"the 2 sorted lists. Key subroutine:MERGE 3/12/2022 9

3/12/2022 9 Merge sort MERGE-SORT A[1 . . n] 1. If n = 1, done. 2. Recursively sort A[ 1 . . n/2 ] and A[ n/2+1 . . n ] . 3. “Merge” the 2 sorted lists. Key subroutine: MERGE

上游充通大粤 Merging two sorted arrays SHANGHAI JIAO TONG UNIVERSITY Subarray 1Subarray 2 20 21 7 2 1 3/12/2022 10

3/12/2022 10 20 13 7 2 Merging two sorted arrays 12 11 9 1 Subarray 1Subarray 2