Question $2$

Assume the array A has indexes $A[1..n].$ Consider the SORTING$-$ALG described below using

pseudocode. State the correct loop invariant for the for loop in line $3($i$.$e$.$ lines $3$ to $5).$

SORTING$-$ALG$(A,n$

for $i=n$ down to $2$

$//$ move the largest element in A$[1..$i$]$ to A$[$i$]$

for $j=1$ to $i-1$

if $A[j]>A[j+1]$

exchange $A[j]$ with $A[j+1]$