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]
Selection Sort Input:A1...; Output:A[1...]sorted in nondecreasing order; ■1.fork-1ton1 ■2. k-6 ■ 3. for衣-什1ton 4. ifAL1<AL灯thenk-i ■ 5. end for; 6. if kithen interchange Ai]and A[ 7.end for;
Selection Sort ◼ Input: A[1…n]; ◼ Output: A[1…n] sorted in nondecreasing order; ◼ 1. for i1 to n-1 ◼ 2. ki; ◼ 3. for ji+1 to n ◼ 4. if A[j]<A[k] then kj; ◼ 5. end for; ◼ 6. if ki then interchange A[i] and A[k]; ◼ 7. end for;
Selection Sort What's the performance of the algorithm Selection Sort? What's the minimum number of comparisons we need and in which case it will happen? v What's the maximum number of comparisons we need and in which case it will happen? What's the minimum number of element assignments? What's the maximum number of element assignments?
Selection Sort ◼ What’s the performance of the algorithm Selection Sort? ✓ 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? ✓ What’s the maximum number of element assignments?