I'm trying to understand the difference between these two conditions for the partition step of quicksort. While writing this out, I'm capitalizing single letter variable names so it's more readable.
In this implementation of quicksort, for simplicity's sake, let's say the pivot_idx = (L + R) // 2, and arr[high] and arr[pivot] are swapped before partitioning. So the L pointer starts at the low index, while the R pointer starts at the high - 1 index. Let's also say the L pointer is incremented until it finds an element that is > pivot, and the next loop decrements the R pointer until it finds an element <= pivot.
If the condition is while (L < R), and we increment the L pointer until it finds an element > pivot, then in the final iteration, L moves forward until it meets R. arr[R] already points to an element that is > pivot, as arr[L] and arr[R] were swapped in the previous step. So the pivot should correctly be placed where L points to at the end.
My function signature is partition(int[] arr, int low, int high). Here is some sample code I wrote.
int pivotIdx = (low + high) / 2;
int pivotElem = arr[pivotIdx];
int r = high - 1;
int l = low;
// Swap pivot and final elem
arr[pivotIdx] = arr[high];
arr[high] = pivotElem;
while (l <= r) {
while (l <= r && arr[l] <= pivotElem) {
l++;
}
while (l <= r && arr[r] > pivotElem) {
r--;
}
if (l < r) {
int tmp = arr[l]; // bigger element
arr[l] = arr[r]; // assign smaller element to left idx
arr[r] = tmp; // assign bigger element to right idx
}
}
arr[high] = arr[l];
arr[l] = pivotElem;
Can it be while (L < R)?
No, it can't.
To see this, try an example with for example int[] arr = { 8, 7 } as input.
8 will be selected as the pivot value and the initial swap with the end element will actually happen to put the array in order.
But then, with while (l < r) instead of while (l <= r), the while loop will not be entered, so the final swap - with the unchanged l value of zero - will put the array back in its original out-of-order state.