Trying figure out why Hoare quick sort works correctly. Basically I can't prove to myself that we can not create an array that will cause fail for Hoare sorting algorithm. Prove not necessary to be 100% mathematics. I just want to believe that algorithm works.
In the code below I rewrite some part of the algorithm to make it more clear to me (the basic idea stay the same).
void quickSort(int[] arr, int start, int end) {
int pivotIndex = partition(arr, start, end);
if (start < pivotIndex - 1) quickSort(arr, start, pivotIndex - 1);
if (end >= pivotIndex) quickSort(arr, pivotIndex, end);
}
int partition(int[] arr, int leftIndex, int rightIndex) {
int pivot = arr[(leftIndex + rightIndex) / 2];
while (true) {
while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;
if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
if (leftIndex > rightIndex) return leftIndex;
}
}
What I'm 100% sure about that function:
- Function shoul partion array into two sub arrays
- low -- contains elements less or equal to pivot
- high -- contains elements greater or qual to pivot
- When partition done, leftIndex couldn't be greater rightIndex more than 1. In other words: leftIndex - rightIndex equals ONLY to 0 or 1.
- Function always returns first index of the first element in high sub array
What I totally don't understand:
First question:
Why if code
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
has been executed, and after that leftIndex becomes equals rightIndex, it doesn't mean that array has been successfully partitioned and we could return leftIndex + 1? To clarify my idea, look at the code below:
int partition(int[] arr, int leftIndex, int rightIndex) {
int pivot = arr[(leftIndex + rightIndex) / 2];
while (true) {
while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;
// remove line from here
//if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
// move it here. If I do that, code stop working and sort array in a wrong way
//sorce array: [6, 3, 12, 10, 3, 8, 5, 8, 11, 2, 9]
//final array: [2, 3, 3, 5, 6, 8, 8, 9, 10, 12, 11] - 12 and 11 at wrong places
if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex > rightIndex) return leftIndex;
}
}
Second question:
Let's imaging the following scenario. Let say pivot value was 10 and code below has been successfully executed:
01 while (arr[leftIndex] < pivot) leftIndex++;
02 while (arr[rightIndex] > pivot) rightIndex--;
03 if (leftIndex == rightIndex) return leftIndex + 1;
After that, let say that leftIndex and rightIndex stoped at element with index X and value = 6 i.e. arr[X] -> 6. Line 3 will return index X + 1 with value, let say 8. So basically we will have sub arrays:
[..., ...] and [8, ..., 10, ...]
So high sub array will contain element less than pivot. Is it possible to create such array to replicate that scenario?
This might answer your overall question about how to prove the Hoare algorithm. This online PDF gives both a formal and an informal proof. Here is the informal one (it's an image because the pdf doesn't have text, it's just an image itself):