G5BADS Informal coursework 3

For tutorials in the week of the 6-10 December:
  1. Consider the following partition algorithm:
    int partition(int[] arr, int l, int r){
       int pivot = arr[r]; // choose pivot to be the last element
       int small = l;  // set at the left border of the range
       int large = r; // set at the right border where the pivot sits
       int temp;     // temporary variable for swapping
       while(small < large) {
          if (arr[small] < pivot) small++;
          else {
             large--;
             // swap the values at small and large
             temp = arr[small];
             arr[small] = arr[large];
             arr[large] = temp;
          }
       }
       // swap the pivot on the border between small and large values
       temp = arr[r];
       arr[r] = arr[large];
       arr[large] = temp;
       return large; // return the border index
    }
    
    Given that
     l < r 
    in the partition method, which of the following are loop invariants of the while loop:
    1. small < r
    2. small < large
    3. small <= large
    4. for all i such that l <= i < small, arr[i] < pivot
    5. for all j such that large <= j <= r, arr[j] >= pivot
    6. for all j such that large < j <= r, arr[j] >= pivot
    
  2. Prove correctness of selection sort:
    
           void  selectionSort(int arr[], int len){
              int i;
              int j;
              int temp;
              int pos_greatest;
    
              for( i = len - 1; i > 0; i--){
                 pos_greatest = 0;
                 for(j = 0; j <= i; j++){
                    if( arr[j] > arr[pos_greatest]){
                       pos_greatest =  j;
                    }//end if
                 }//end inner for loop
                 temp = arr[i];
                 arr[i] = arr[pos_greatest];
                 arr[pos_greatest] = temp;
              }//end outer for loop
           }//end selection sort