Can any guru here give me a working C example for non-recursive quicksort? Actually there is a non-recursive quicksort example from the book "Algorithms in C" by Robert Sedgewick. Here is the code,
But it doesn't work. Any improvement to make it work? Thanks so much!Code:int top = -1;
struct s
{
int a;
int b;
}stack[100];
void push(int x, int y)
{
top++;
stack[top].a = x;
stack[top].b = y;
}
void pop(int& x, int& y)
{
x = stack[top].a;
y = stack[top].b;
top--;
}
int partition(int a[], int l, int r)
{
int i = l-1;
int j = r;
int v = a[r];
for(;;)
{
while(a[++i] < v);
while(a[--j] > v && j>l && j > i);
if(j<=l || j<=i)
break;
swap(a[i], a[j]);
}
swap(a[i], a[r]);
return i;
}
void quicksort(int a[], int l, int r)
{
int i;
push(r, l);
while(top!=-1)
{
pop(l, r);
if(r <= l)
continue;
i = partition(a, l, r);
if(i-l > r-i)
{
push(l, i-1);
push(i+1, r);
}
else
{
push(i+1, r);
push(l, i-1);
}
}
}
