Question: Using the algorithm we outlined in class, what will be the result after we pivot on 35?
35 57 53 26 50 15 22 21 25 14 11 2
Hint: Here is some code from class to do a single pivot operation, when the pivot is at pivot_loc.
int pivot = arr[pivot_loc];
swap(arr[pivot_loc], arr[0]);
int l = 1;
int r = n - 1;
while(l < r) {
// INVARIANT: all left of l <= pivot, all right of r > pivot
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]);