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