Note: For this class, the word "comparison" refers only to comparisons involving list elements. For example ifai and aj are list elements in a list of length n, the code "if aidj " performs one comparison. Similarly the code "if ai5" performs one comparison. However, we would say the code i" performs no comparisons because it is not making a comparison involving a list element 1. This problem refers to the following three sorting algorithms. procedure InsertionSortA(a, a2,... .an: a list of real numbers with n22) for j := 2 to n 3. while aj > a i:= i + 1 m:= aj 6. for k: 0 toj-i-1 8. procedure lnsertionSortB(al.a2..-.. an: a list of real nuinbers with n > 2) 1. for r2 to n while aj ac then i := c + 1 else b := c 6. 9, for k := 0 to j-i-1 10 11.am (a) (2 points) Suppose we start with the list of real numbers 1,5,4,4,2,5 and run one of these algo- rithms to sort it. We stop the program after 3 iterations of the outer loop, and we see that the list now looks like 1,4,4,5,2,5. Which algorithm(s) could have been used to sort the list? Explain. (b) (2 points) For each algorithm given in part (a), how many comparisons between list elements were performed by the algorithm at the time we stopped the program? Justify your answer by showing which comparisons are performed. (c) (6 points) For each of the three algorithms, state a loop invariant that could be used to show the algorithm correctly solves the sorting problem. Just state the loop invariant; you do not need to prove it Loop Invariant for InsertionSortA: After the iteration of the outer loop... Loop Invariant for InsertionSortB: After the th iteration of the outer loop... LoopInvariant for InsertionSortC: After theteration of the outer loop... Note: For this class, the word "comparison" refers only to comparisons involving list elements. For example ifai and aj are list elements in a list of length n, the code "if aidj " performs one comparison. Similarly the code "if ai5" performs one comparison. However, we would say the code i" performs no comparisons because it is not making a comparison involving a list element 1. This problem refers to the following three sorting algorithms. procedure InsertionSortA(a, a2,... .an: a list of real numbers with n22) for j := 2 to n 3. while aj > a i:= i + 1 m:= aj 6. for k: 0 toj-i-1 8. procedure lnsertionSortB(al.a2..-.. an: a list of real nuinbers with n > 2) 1. for r2 to n while aj ac then i := c + 1 else b := c 6. 9, for k := 0 to j-i-1 10 11.am (a) (2 points) Suppose we start with the list of real numbers 1,5,4,4,2,5 and run one of these algo- rithms to sort it. We stop the program after 3 iterations of the outer loop, and we see that the list now looks like 1,4,4,5,2,5. Which algorithm(s) could have been used to sort the list? Explain. (b) (2 points) For each algorithm given in part (a), how many comparisons between list elements were performed by the algorithm at the time we stopped the program? Justify your answer by showing which comparisons are performed. (c) (6 points) For each of the three algorithms, state a loop invariant that could be used to show the algorithm correctly solves the sorting problem. Just state the loop invariant; you do not need to prove it Loop Invariant for InsertionSortA: After the iteration of the outer loop... Loop Invariant for InsertionSortB: After the th iteration of the outer loop... LoopInvariant for InsertionSortC: After theteration of the outer loop