nonrecursive quick sort

This is a discussion on nonrecursive quick sort within the C++ Programming forums, part of the General Programming Boards category; Hello, sorry to open same question on this forum but, I have no choice since I'm trying to implement nonrecursive ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    nonrecursive quick sort

    Hello, sorry to open same question on this forum but, I have no choice since I'm trying to implement nonrecursive quicksort using C++ STL.

    i'm trying to correct code earlier posted on the board,
    Quicksort
    but I have problem with an infinite loop:
    Code:
    #include <stack>
    /*...*/
    void quicksort_it(int *dataset,int dataset_size)
    {
    	stack<int> st;
    	int i,j,first,last,pivot;
    	
    	for(i=0;i<dataset_size;i++)
    		st.push(dataset[i]);
    		
    	first= 0;
    	last = dataset_size-1;
    	while(!(st.empty()))
    	{
    		for(i=first;i<=last;i++)
    		{
    			dataset[i] = st.top();
    			st.pop();
    		}
    		while(first<last)
    		{
    			// Split
    			pivot = dataset[first];
    			i = first, j= last -1 ;
    			for(;;)
    			{
    				while(dataset[i] <= pivot && i <= last) {i++;}
    				while(pivot < dataset[j] && j >= first){j--;}
    				if(i<j)
    					swap(dataset[i],dataset[j]);
    				else
    					break;
    			}
    			swap(dataset[i],dataset[last-1]);
    			for(i=pivot+1;i<=last;i++)
    				st.push(dataset[i]);
    			pivot=last-1;
    		}
    	}
    }
    Please can you look this and correct it, I don't know what is wrong.
    Thanks

  2. #2
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Code:
    while(first<last)
    {
    // Split
    You never update either first or last, so if you enter this while loop, you'll stay in it forever.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Well, I think I made it.
    Code:
    void quicksort_it(int *dataset,int l,int r)
    {
    	stack<int> st;
    	int j;
    	st.push(r);
    	st.push(l);
    	while(!st.empty())
    	{
    		l=st.top();
    		st.pop();
    		r=st.top();
    		st.pop();
    
    		j=partition(dataset,l,r);
    
    		if(l < (j-1))
    		{
    			st.push(j-1);
    			st.push(l);
    		}
    		if((j+1) < r)
    		{
    			st.push(r);
    			st.push(j+1);
    		}
    	}
    	
    }
    
    int partition(int* array, int l, int r)
     {
    	 int pivot,i,j;
    
    	
    	pivot=array[l];
    	 i=l+1;
    	 j=r;
    
    	 for(;;)
    	 {
    		 while((array[i] <= pivot) && (i <= r))i++;
    		 while((array[j] > pivot) && (j > l))j--;
    		
    		 if(i < j)
    			 swap_in_array(array,i,j);
    		 else 
    			 break;
    	 }
    	 swap_in_array(array,j,l);
    
    	 return j;
     }
    
      void swap_in_array(int* array, int i, int j)
     {
    	 int tmp;
    	 tmp=array[i];
    	 array[i]=array[j];
    	 array[j]=tmp;
     }
    I think this is correct.
    All I need was a good sleep.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive quick sort - stack overflow
    By Micko in forum C Programming
    Replies: 9
    Last Post: 01-01-2005, 05:51 PM
  2. nonrecursive quick sort
    By Micko in forum C Programming
    Replies: 8
    Last Post: 12-29-2004, 05:50 PM
  3. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 10:51 AM
  4. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 10:06 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21