What's the mistake in this quick implementation?
The code works for a few test cases, but not most. Where am I going wrong?
Also if something can be done to make the code more efficient.
void quicksort(int *a, int a1, int b1)
{
if ((b1 - a1) > 0)
{
int pivot = (a1 + b1) / 2;
int i = a1;
int j = b1;
while (i <= j)
{
while (a[i] < a[pivot]) //left to right
i++;
while (a[j] > a[pivot]) //right to left
j--;
if (i < j) // swapping
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
quicksort(a, a1, j);
quicksort(a, i, b1); //recursive calls
}
}
source to share
You are not considering the case where i == j
, and also as @MK's comment in the summary says, the value should be a value, not an index ( pivot = (a1+b1)/2;
should be something like pivot = a[(a1+b1)/2]
).
For example, if you run an array a = {2, 45, 56, 3, 125}
(array, you specify in comments), your implementation can be transformed into {2, 3, 45, 56, 125}
using i = 2
, j = 2
and pivot = 2
(considered as the index). In this case, the program will go into an infinite loop, because it never enters the last block if
.
If you change the internal condition if on i <= j
, it must be right.
Finally, with some minor optimizations applied, your code should look like this:
void quicksort(int *a, int a1, int b1)
{
if (b1 > a1) // one less operation (subtraction) with respect to the original
{
int pivot = a[a1 + ((b1 - a1) / 2)]; // it is now a value and not an index. the index is calculated in this way to avoid an arithmetic overflow
int i = a1;
int j = b1;
while (i <= j)
{
while (a[i] < pivot) //left to right
i++;
while (a[j] > pivot) //right to left
j--;
if (i <= j) // swapping
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
quicksort(a, a1, j);
quicksort(a, i, b1); //recursive calls
}
}
As a final optimization, I suggest optimizing the tail call .
Let me know if anything is unclear.
source to share