Non-recursive quicksort
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Non-recursive quicksort

  1. #1
    Join Date
    Jul 2005
    Posts
    910

    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. #2
    Join Date
    Oct 2006
    Posts
    616

    Re: Non-recursive quicksort

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

    Regards,
    Zachm

  3. #3
    Join Date
    Jul 2005
    Posts
    910

    Re: Non-recursive quicksort

    Thanks for the link. I think it is a good one.
    Quote Originally Posted by Zachm View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center