-
April 10th, 2010, 10:23 PM
#1
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.
-
April 10th, 2010, 11:05 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
-
April 12th, 2010, 04:30 PM
#3
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|