Loop Invariants

The csort function contains several loops, including one set of nested loops. Its operation is destructive to the contents of the starting vector, so in order to prove the correctness of this algorithm, we need to establish meaningful loop invariants. Note that the notation A$[$i$...$j$]$ refers to elements i through j in vector A$,$ inclusive.

In this problem we should assert, among other things, that our code does not change the overall number of occurrences of each distinct grade. You will complete the rest of the loop invariant in the problem below.

The purpose of the loop occupying lines $5$ through $7$ is simply to initialize the value of each index of H to zero. We will not bother to determine a loop invariant for this, nor prove its correctness.

Here we describe an invariant for the loop occupying lines $9$ through $11($Invariant H$).$ Choose the most appropriate selections from the dropdown boxes:

At the start of the iteration described by the variable

$,$ index

$1$

of the array H contains the number of occurrences of the value

$1$

in the array A$[0..$j$-1].$