Consider the nave sorting algorithm we presented in Module 1:

Sort-Array(A)

for j = 1 to (A.length 1)

for i = (j + 1) to A.length

if (A[i] < A[j])

// swap A[i] and A[j]

buffer = A[j]

A[j] = A[i]

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 exercise.

1. Express the property that Sort-Array(A) must satisfy to be correct:
2. 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. 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:
   1. Initialization
   2. Maintenance
   3. Termination