Exercise 4 (35 points) Loop Invariant

Please answer the following loop invariant question, and provide justifications.

Exercise 4 (35 points) Loop Invariant Consider the naive sorting algorithm we presented in Module l Sort-Array (A) for j = 1 to (A.length - 1) for i= (j + 1) to A. length // swap A[il and Aj] buffer = A[j] A[i] -buffer The objective is to prove that the above sorting algorithm is correct. Consider getting inspiration from the textbook in Section 2.1: the author shows that the Insert Sort algorithm is correct using loop invariants. This should help you with this exerc ise. I) (2 points) Express the property that Sort-Array (A) must satisfy to be correct 2) (4 points) Can you find some loop invariants for the outer for loop? List these invariants (even if they are not that helpful for our ultimate proof of correctness of Sort-Array) 3) (9 points) Propose a loop invariant for the outer loop that is the closest to our ultimate objective Sort-Array is correct 4) Use the three steps: a. (4 pointsilization b. (10 points) Maintenance c. (6 points)Termination Exercise 4 (35 points) Loop Invariant Consider the naive sorting algorithm we presented in Module l Sort-Array (A) for j = 1 to (A.length - 1) for i= (j + 1) to A. length // swap A[il and Aj] buffer = A[j] A[i] -buffer The objective is to prove that the above sorting algorithm is correct. Consider getting inspiration from the textbook in Section 2.1: the author shows that the Insert Sort algorithm is correct using loop invariants. This should help you with this exerc ise. I) (2 points) Express the property that Sort-Array (A) must satisfy to be correct 2) (4 points) Can you find some loop invariants for the outer for loop? List these invariants (even if they are not that helpful for our ultimate proof of correctness of Sort-Array) 3) (9 points) Propose a loop invariant for the outer loop that is the closest to our ultimate objective Sort-Array is correct 4) Use the three steps: a. (4 pointsilization b. (10 points) Maintenance c. (6 points)Termination