Exercise $2(70$ points$)$ Loop Invariant

Consider the algorithm getIndexMaximum $(A,k)$ that takes a sequence $A$ as an input and returns the index of the largest number $($maximum$)$ in the range $[$k$-$A$.$length$]$ in Sequence A$.$

For example, let $A=\{100,2,14,5,22,7\}.$ getIndexMaximum $(A,3)$ will return $5$ because $5$ is the index of the element $22$ and $22$ is the largest number in $A$ in the range $[3-6].$

Consider the following sorting algorithm that sorts a sequence A in decreasing order:

Sort$-$Array $($A$)$

for $i=1$ to $A.$ length

IndexMax $=$getIndexMa$m(A,i)$

$//$ swap A$[$i$]$ and A$[$IndexMin$]$

buffer IndexMax