just learned and implemented Hoare's partitioning scheme for quicksort in Java. Works as good as advertised lol, but I just have a couple questions about it. I tried looking up a youtube video on it, but didn't find any that explained it well to me.
I think in Hoare's actual partition, the pivot is supposed to be the first element, but I used the middle element as a pivot just in case the array is already sorted. I wrote some comments in the code on what Im a bit confused about. Mainly why i and j are set to 1 lower and 1 higher than low and high if theyre just incremented and decremented before checking the array.
public static void quicksort(int [] arr, int low, int high){
if(low < high){
int pivot = partition(arr, low, high);
quicksort(arr, low, pivot);
quicksort(arr, pivot+1, high);
}
}
public static int partition(int [] arr, int low, int high){
int i = low-1; //Why not just set i to low?
int j = high+1;// Why do you have to set it to high+1 and not high?
int mid = low + (high-low)/2;
int pivot = arr[mid];
while(true){
do {
i++;
} while(arr[i] < pivot);
do {
j--;
} while(arr[j] > pivot);
if( i >= j) return j;
swap(arr, i, j);
}
}
But when I change the partitioning code to what it is below, it ends up running seemingly forever with bigger sized arrays, for example with 17 different numbers, and I need to manually stop it. The weird thing is that this code will work for smaller sized array, for example with 6 numbers in it, but not larger sized arrays. I can't manually go through the code for arrays with a lot of numbers because I get lost in the recursion calls.
public static int partition(int [] arr, int low, int high){
int i = low;
int j = high;
int mid = low + (high-low)/2;
int pivot = arr[mid];
while(true){
while(arr[i] < pivot){
i++;
}
while(arr[j] > pivot){
j--;
}
if( i >= j) return j;
swap(arr, i, j);
}
}
So just hoping someone can let me know why the top one works perfectly and the bottom one doesn't.
The important thing here is that after a swap has been performed of a[i] and a[j], those two indexes should first be incremented/decremented before doing the next comparison with the pivot.
This doesn't happen in your second version.
This is however necessary. Imagine that at a certain moment both a[i] and a[j] are equal to the pivot value (because there are duplicate values). Then the swap will happen, but it will not change anything. What is worse, in your second version the comparison with the pivot value will again show that they are equal, and we're back to where we were: this becomes an infinite loop. If however there is at least one execution of i++ and j-- after a swap has occurred, such an infinite loop will not occur.
One way to ensure that i++ and j-- happen at least once after a swap, is to place them in a do { } while loop. And once you have made that choice, it is evident that the first time i must be one less than low and j one more than high.