## 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
```