Why does this Quicksort work?
Posted
by IVlad
on Stack Overflow
See other posts from Stack Overflow
or by IVlad
Published on 2010-05-21T13:21:26Z
Indexed on
2010/05/21
14:00 UTC
Read the original article
Hit count: 290
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?
© Stack Overflow or respective owner