Question: Write invariants at the indicated space in the following functions.
void
pivot(int *arr, int n, int pivot) {
swap(arr[pivot_loc], arr[0]);
int l = 1;
int r = n - 1;
while(l < r) {
// INVARIANT: ???
while(l < r && arr[l] <= pivot) l++;
while(r > l && arr[r] > pivot) r--;
if(l < r) {
swap(arr[r], arr[l]);
l++;
r--;
}
}
if(arr[l] <= pivot) swap(arr[0], arr[l]);
else swap(arr[0], arr[l - 1]);
}
Answer: For every element of the array whose position before entering the loop is i, if i<l or i>r, then the element is currently in a position less than l if the element is less than or equal to pivot and in a position greater than r if the element is greater than pivot.