After a while, I was trying to implement quickSort on my own. To me the implementation looks fine, but some test cases are apparently failing.
class MyImplementation {
public int[] sortArray(int[] nums) {
quicksort(nums, 0, nums.length - 1);
return nums;
}
private void quicksort(int[] nums, int lo, int hi){
if(lo < hi){
int j = partition(nums, lo, hi);
quicksort(nums, lo, j-1);
quicksort(nums, j+1, hi);
}
}
private int partition(int[] nums, int lo, int hi){
int pivot = nums[lo];
int head = lo + 1;
int tail = hi;
while(head < tail){
while(head < hi && nums[head] < pivot) ++head;
while(nums[tail] > pivot) --tail;
if(head < tail){
swap(nums, head, tail);
++head;
--tail;
}
}
if(nums[head] < pivot)
swap(nums, lo, head);
else
swap(nums, lo, head - 1);
return head;
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
It's passing in many cases, like these :-
[5,2,3,1]
[5,1,1,2,0,0]
[7,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5]
but it's failing in the following test cases :-
[5,71,1,91,10,2,0,0,13,45,7]
the output I am getting is :-
[0,0,1,2,5,10,7,71,13,45,91]
instead of :-
[0,0,1,2,5,7,10,13,45,71,91]
I know, I can copy from somewhere to get the correctly working code, but can we figure out why this code is not working from an Algorithmic point of view!! What is the logical flaw in this code? How can we fix this with minimum changes and get a perfectly working code?
That's quite subtle. The bug is here:
private void quicksort(int[] nums, int lo, int hi){
if(lo < hi){
int j = partition(nums, lo, hi);
quicksort(nums, lo, j-1);
quicksort(nums, j+1, hi);
// ^^^ j+1 must be j
}
}
The most subtle part is that it is not in general necessary to use j as the starting point of the "high" part to recurse on, but your partitioning algorithm requires it. So you will see various examples that recurse on different partitions, and they can be correct as well, in combination with whatever partitioning algorithm they use, but there is not much freedom to mix.
Your partitioning algorithm is based on Hoare's partitioning algorithm (see below), not Lomuto's algorithm. Lomuto's partitioning algorithm puts the pivot in its final position and returns its index, so that index can be skipped in the recursion. Hoare's partitioning algorithm, or your variant of it, does not quite do that. Eg in the case that the else branch at the end of your partitioning algorithm is taken, the pivot ends up at head - 1, while element at head has some arbitrary value not-less-than the pivot, all we know is that it belongs in the "high" partition but it has not been sorted yet and cannot be skipped.
In combination with Hoare's partitioning, it is common to see the recursion on [lo .. p] (where p is the index returned by the partitioning algorithm) and [p+1 .. hi], but that is not suitable in this case because your version of it returns head instead of tail, effectively making p one higher, so the partitions become [lo .. p-1] and [p .. hi].
As for this being similar to Hoare partitioning, consider that the important part of this partitioning algorithm looks like this:
while(head < tail){
while(head < hi && nums[head] < pivot) ++head;
while(nums[tail] > pivot) --tail;
if(head < tail){
swap(nums, head, tail);
++head;
--tail;
}
}
And how does Hoare's partition algorithm work, well, the same way really (from wikipedia):
loop forever
// Move the left index to the right at least once and while the element at
// the left index is less than the pivot
do i := i + 1 while A[i] < pivot
// Move the right index to the left at least once and while the element at
// the right index is greater than the pivot
do j := j - 1 while A[j] > pivot
// If the indices crossed, return
if i >= j then return j
// Swap the elements at the left and right indices
swap A[i] with A[j]
This uses an early-exit instead of a while-loop as the outer loop, and therefore doesn't need an if around the swap, but apart from such minor details, it is the same thing.
If it is expressed this way, as opposed to how it is expressed in this question, it is less reasonable to modify it to always return the pivot index (expressed this way, it is also much less obvious what guarantee it actually makes on its return value). With the variant found in this question, that sort of naturally falls out as a possible modification, as seen in trincots answer.
By contrast, the important part of Lomuto's partitioning algorithm works like this (also from wikipedia)
for j := lo to hi - 1 do
// If the current element is less than or equal to the pivot
if A[j] <= pivot then
// Move the temporary pivot index forward
i := i + 1
// Swap the current element with the element at the temporary pivot index
swap A[i] with A[j]
This is based on a totally different principle.