Merging Two Sorted Lists What's the performance of the algorithm Merging Two Sorted Lists? v What's the minimum number of comparisons we need and in which case it will happen? vWhat's the maximum number of comparisons we need and in which case it will happen? vWhat's the minimum number of element assignments we need and in which case it will happen? vWhat's the maximum number of element assignments we need and in which case it will happen?
Merging Two Sorted Lists ◼ What’s the performance of the algorithm Merging Two Sorted Lists? ✓ What’s the minimum number of comparisons we need and in which case it will happen? ✓ What’s the maximum number of comparisons we need and in which case it will happen? ✓ What’s the minimum number of element assignments we need and in which case it will happen? ✓ What’s the maximum number of element assignments we need and in which case it will happen?
Merging Two Sorted Lists The number of element comparisons performed by Algorithm MERGE to merge two nonempty arrays of sizes n and n,respectively,where nsm,into one sorted array of size nm+is between n and n-1
Merging Two Sorted Lists ◼ The number of element comparisons performed by Algorithm MERGE to merge two nonempty arrays of sizes n1 and n2 , respectively, where n1n2 , into one sorted array of size n=n1+n2 is between n1 and n-1
Merging Two Sorted Lists The number of element assignments performed by Algorithm MERGE to merge two arrays into one sorted array of size n is exactly 2n
Merging Two Sorted Lists ◼ The number of element assignments performed by Algorithm MERGE to merge two arrays into one sorted array of size n is exactly 2n
Problems and Algorithms Each algorithm is designed to solve one problem,but for one problem,we can design many different algorithms. What's the difference of these algorithms? v Why we design different algorithms for the same problem? Example Problem:Sort √Selection Sort √Insertion Sort Bottom-Up Merge Sorting
Problems and Algorithms ◼ Each algorithm is designed to solve one problem, but for one problem, we can design many different algorithms. ✓ Selection Sort ✓ Insertion Sort ✓ Bottom-Up Merge Sorting Example Problem: Sort ✓ What’s the difference of these algorithms? ✓ Why we design different algorithms for the same problem?
Selection Sort Let A[1...n]be an array of n elements. A simple and straightforward algorithm to sort the entries in A works as follows. First,we find the minimum element and store it in AL1]. Next,we find the minimum of the remaining n1 elements and store it in A[2]. We continue this way until the second largest element is stored in An-1]
Selection Sort ◼ Let A[1…n] be an array of n elements. ◼ A simple and straightforward algorithm to sort the entries in A works as follows. ◼ First, we find the minimum element and store it in A[1]. ◼ Next, we find the minimum of the remaining n-1 elements and store it in A[2]. ◼ We continue this way until the second largest element is stored in A[n-1]