Hi,
I’ve written a quicksort algorithm based off of a book. I’ve so far understood it, except for one line, which doesn’t make sense to me yet.
private void sort(int left, int right) {
if (right - left <= 0) { //only one element exist
return;
} else {
int pivot = this.array[right]; //right most item in the array
int partition = this.partition(left, right, pivot);
this.sort(left, partition - 1);
this.sort(partition + 1, right);
}
}
private void swap(int index1, int index2) {
int temp = this.array[index1];
this.array[index1] = this.array[index2];
this.array[index2] = temp;
}
private int partition(int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while(true) {
while (this.array[++leftPtr] < pivot); //find a value that is bigger than the pivot
while (rightPtr > 0 && this.array[--rightPtr] > pivot); //find a value that is less than the pivot
if (leftPtr >= rightPtr) { //they crossed each other
break;
} else {
this.swap(leftPtr, rightPtr);
}
}
this.swap(leftPtr, right); // ???
return leftPtr;
}
In order for the algorithm to work correctly, in the partition method, I need to swap once more before returning the left partition. It looks like I have to swap the last iteration of leftPtr with the furthest right element in the array.
But the problem is, the right most element has already been swapped with another element, meaning that it belongs there, over the pivot. By swapping them once more, I’m actually putting a value that may or may not belong above the pivot. It’s blindly swapping them. Hope that makes sense and someone can shed some light.