2.1 Insertion Sort and Inversions (15 pts) The Insertion Sort algorithm is as follows Input: An array A-[a 1,a 2, ,a n of n elements Output The array A in sorted order for i-2 to n Initialize j while(j 1 & AIj-11 AIj]) swap A and AIj] set j-j-1 Return A In this problem we will do a finer analysis of Insertion Sort and show that it runs fast on nearly sorted data. 1. An iversion in an array A a,aan] is a pair (a,, a,) such that i a. For example, in the array 4, 2,5, 3 there are three inversions. A sorted array has no inversions, and more generally, the number of inversions is a measure of how well-sorted" an array is. Prove that after every comparison made by Insertion Sort, the number of inversions in the array decreases by at most 1 2. Lower bound: Based on part 1, prove that the Insertion Sort algorithm, when given as input an array A of n 3. Prove that after every comparison made by Insertion Sort, either the number of inversions in the array decreases 4. Upper bound: Based on part 3, prove that the Insertion Sort algorithm, when given as input an array A of n 5. Hence on any input with 1 inversions, the running time of Insertion Sort is lower bounded by (1) and upper elements and having I inversions, must perform at least I comparisons by 1 or the loop variable i (see the algorithm above increases by 1 elements and having I inversions, will perform at most nI 1comparisons bounded by O(n -I+1). Show that if each element in the input array is at most k positions away from its final position in the sorted array then the number of inversions is O (n), thereby implying that Insertion Sort will run in O(nk) time on such an array. If you need to you can assume that all the elements in the array are distinct. 2.1 Insertion Sort and Inversions (15 pts) The Insertion Sort algorithm is as follows Input: An array A-[a 1,a 2, ,a n of n elements Output The array A in sorted order for i-2 to n Initialize j while(j 1 & AIj-11 AIj]) swap A and AIj] set j-j-1 Return A In this problem we will do a finer analysis of Insertion Sort and show that it runs fast on nearly sorted data. 1. An iversion in an array A a,aan] is a pair (a,, a,) such that i a. For example, in the array 4, 2,5, 3 there are three inversions. A sorted array has no inversions, and more generally, the number of inversions is a measure of how well-sorted" an array is. Prove that after every comparison made by Insertion Sort, the number of inversions in the array decreases by at most 1 2. Lower bound: Based on part 1, prove that the Insertion Sort algorithm, when given as input an array A of n 3. Prove that after every comparison made by Insertion Sort, either the number of inversions in the array decreases 4. Upper bound: Based on part 3, prove that the Insertion Sort algorithm, when given as input an array A of n 5. Hence on any input with 1 inversions, the running time of Insertion Sort is lower bounded by (1) and upper elements and having I inversions, must perform at least I comparisons by 1 or the loop variable i (see the algorithm above increases by 1 elements and having I inversions, will perform at most nI 1comparisons bounded by O(n -I+1). Show that if each element in the input array is at most k positions away from its final position in the sorted array then the number of inversions is O (n), thereby implying that Insertion Sort will run in O(nk) time on such an array. If you need to you can assume that all the elements in the array are distinct