CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Senior Member
Join Date
Jul 2005
Posts
1,030

## Non-recursive quicksort

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,
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);
}
}
}```
But it doesn't work. Any improvement to make it work? Thanks so much!
Last edited by LarryChen; April 10th, 2010 at 10:27 PM.

2. ## Re: Non-recursive quicksort

Haven't really had a look on the code you posted, but maybe have a look here ?

Regards,
Zachm

3. Senior Member
Join Date
Jul 2005
Posts
1,030

## Re: Non-recursive quicksort

Thanks for the link. I think it is a good one.
Originally Posted by Zachm
Haven't really had a look on the code you posted, but maybe have a look here ?

Regards,
Zachm

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•