Reputation: 784
Trying to figure out why Hoare partition algorithm always splits an array into two right parts. In code below, I extend Hoare algorithm
to make it more clear to me (see comments for details)
int partition(int[] arr, int leftIndex, int rightIndex) {
int pivot = arr[(leftIndex + rightIndex) / 2];
while (leftIndex <= rightIndex) {
while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;
// If all numbers at right places, than leftIndex and rightIndex
// could point at same array element index
// So it's means partion done.
// We should return leftIndex + 1 cause
// rightIndex points at the last element of the left sub array
if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
}
//But here the tricky thing: Why does this "if case" never execute?
if (leftIndex - 1 > rightIndex)
System.out.println("leftIndex - 1 > rightIndex");
return leftIndex;
}
So the question is: Is it possible to pass an array to partition function, so the line below will be executed?
if (leftIndex - 1 > rightIndex)
System.out.println("leftIndex - 1 > rightIndex");?
Upvotes: 0
Views: 417
Reputation: 2897
For that to execute, leftIndex would have to be at least rightIndex + 2, and that just can't happen, assuming we start the function with leftIndex <= rightIndex:
With these two loops:
while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;
The indices can never cross each other - if not sooner, they'll stop at either side of the pivot.
Then we leave the function if this is the case:
if (leftIndex == rightIndex) return leftIndex + 1;
So, the only thing that remains is:
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
Even if they're as close as can be (leftIndex == rightIndex - 1
), after that executes they'll be at leftIndex == rightIndex + 1
. And we still didn't get a difference of 2.
Upvotes: 2