Why does this Quicksort work?
- by IVlad
I find this Quicksort partitioning approach confusing and wrong, yet it seems to work. I am referring to this pseudocode. Note: they also have a C implementation at the end of the article, but it's very different from their pseudocode, so I don't care about that.
I have also written it in C like this, trying to stay true to the pseudocode as much as possible, even if that means doing some weird C stuff:
#include <stdio.h>
int partition(int a[], int p, int r)
{
int x = a[p];
int i = p - 1;
int j = r + 1;
while (1)
{
do
j = j - 1;
while (!(a[j] <= x));
do
i = i + 1;
while (!(a[i] >= x));
if (i < j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
else
{
for (i = 1; i <= a[0]; ++i)
printf("%d ", a[i]);
printf("- %d\n", j);
return j;
}
}
}
int main()
{
int a[100] = //{8, 6,10,13,15,8,3,2,12};
{7, 7, 6, 2, 3, 8, 4, 1};
partition(a, 1, a[0]);
return 0;
}
If you run this, you'll get the following output:
1 6 2 3 4 8 7 - 5
However, this is wrong, isn't it? Clearly a[5] does not have all the values before it lower than it, since a[2] = 6 > a[5] = 4. Not to mention that 7 is supposed to be the pivot (the initial a[p]) and yet its position is both incorrect and lost.
The following partition algorithm is taken from wikipedia:
int partition2(int a[], int p, int r)
{
int x = a[r];
int store = p;
for (int i = p; i < r; ++i)
{
if (a[i] <= x)
{
int t = a[i];
a[i] = a[store];
a[store] = t;
++store;
}
}
int t = a[r];
a[r] = a[store];
a[store] = t;
for (int i = 1; i <= a[0]; ++i)
printf("%d ", a[i]);
printf("- %d\n", store);
return store;
}
And produces this output:
1 6 2 3 8 4 7 - 1
Which is a correct result in my opinion: the pivot (a[r] = a[7]) has reached its final position.
However, if I use the initial partitioning function in the following algorithm:
void Quicksort(int a[], int p, int r)
{
if (p < r)
{
int q = partition(a, p, r); // initial partitioning function
Quicksort(a, p, q);
Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r.
}
}
... it seems to be a correct sorting algorithm. I tested it out on a lot of random inputs, including all 0-1 arrays of length 20.
I have also tried using this partition function for a selection algorithm, in which it failed to produce correct results. It seems to work and it's even very fast as part of the quicksort algorithm however.
So my questions are:
Can anyone post an example on which the algorithm DOESN'T work?
If not, why does it work, since the partitioning part seems to be wrong? Is this another partitioning approach that I don't know about?
