1. void simpleSort (int A[]) {
     for (int i = 0; i < A.length; i++) {
       for (int j = 0; j < i; j++) {
         if (A[i] < A[j]) {
           int temp = A[i];
           A[i] = A[j];
           A[j] = temp;
         }
       }
     }
   }
   

2. void bubbleSort (int A[]) {
     int bound = A.length;
     while (bound > 0) {
       int t = 0;
       for (int i = 0; i < bound-1; i++) {
         if (A[i] > A[i+1]) {
           int swap = A[i];
           A[i] = A[i+1];
           A[i+1] = swap;
           t = i+1;
         }
       }
       bound = t;
     }
   }
   

3. void selectionSort (int A[]) {
     for (int i = A.length-1; i > 0; i--) {
       int max = i;
       for (int j = i-1; j >= 0; j--) {
         if (A[j] > A[max])
           max = j;
       }
       int swap = A[max];
       A[max] = A[i];
       A[i] = swap;
     }
   }
   

Part II

Each algorithm consists of two loops. For each algorithm, give the necessary loop invariant for both the inner and the outer loop. You do this by first determining precisely what we need to be true when the loop terminates (that is, when the loop condition becomes false). For example, when the outer loop for each algorithm terminates, we need to have the array be in sorted order.

You have the loop invariant correct if it is true before you enter the loop, is true after each iteration of the loop, and most importantly if we combine the fact that the loop invariant is true with the fact that the loop condition is false we immediately get our goal for the termination of the loop. You do not have to prove the loop invariant or justify it.