Quicksort

This is a discussion on Quicksort within the C++ Programming forums, part of the General Programming Boards category; Hi, i'm trying to implement a nonrecursive quicksort. I have written this code but it doesn't work. It simply doesn't ...

  1. #1
    Registered User
    Join Date
    May 2002
    Posts
    21

    Quicksort

    Hi, i'm trying to implement a nonrecursive quicksort. I have written this code but it doesn't work. It simply doesn't sort the array. Can you give same advice?
    Code:
    void quicksort_it(int *dataset,int dataset_size)
    {
    	StackType<int> stack;
    	int i,j,first,last,pivot;
    	
    	for(i=0;i<dataset_size;i++)
    		stack.Push(dataset[i]);
    		
    	first= 0;
    	last = dataset_size-1;
    	while(!(stack.IsEmpty()))
    	{
    		for(i=first;i<=last;i++)
    			dataset[i] = stack.Pop();
    		while(first<last)
    		{
    			// Split
    			pivot = median3(dataset, first, last);
    			i = first, j= last -1 ;
    			for(;;)
    			{
    				while(dataset[++i] <pivot) {};
    				while(pivot<dataset [--j]){};
    				if(i<j)
    					swap(dataset[i],dataset[j]);
    				else
    					break;
    			}
    			swap(dataset[i],dataset[last-1]);
    			for(i=pivot+1;i<=last;i++)
    				stack.Push(dataset[i]);
    			last = pivot-1;
    		}
    	}
    }
    
    const int & median3( int *dataset, int left, int right )
    {
    	int center = ( left + right ) / 2;
            if( dataset[ center ] < dataset[ left ] )
                swap( dataset[ left ], dataset[ center ] );
            if( dataset[ right ] < dataset[ left ] )
                swap( dataset[ left ], dataset[ right ] );
            if( dataset[ right ] < dataset[ center ] )
                swap( dataset[ center ], dataset[ right ] );
    
            // Place pivot at position right - 1
              swap( dataset[ center ], dataset[ right - 1 ] );
              return dataset[ right - 1 ];
    }

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    since you're using the stl, you should know that it includes a pretty fast sort already... i think its a combination q-sort and some kind of smaller sort.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  2. Problems with Quicksort and Pointers
    By algatt in forum C Programming
    Replies: 3
    Last Post: 10-10-2007, 05:24 AM
  3. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 10:33 AM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 03:02 PM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 09:42 AM

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