Quicksort question

This is a discussion on Quicksort question within the C++ Programming forums, part of the General Programming Boards category; i have been working on an implimentation of quicksort for the past few minutes, and i have what appears to ...

  1. #1
    ...
    ... is offline
    Registered User
    Join Date
    Feb 2002
    Posts
    465

    Quicksort question

    i have been working on an implimentation of quicksort for the past few minutes, and i have what appears to be a correct implimentation of the algorithm, and yet it doesnt quite sort 100%... it works like a dream for a large number of items, but small numbers tend to get sorted with a slight bit of inaccuracy ( the smaller the number of items, the less accurate ). here is the code i have, any ideas what my problem might be?

    Code:
    template <typename Type>
    void Swap( Type &a, Type &b )
    {
    	Type temp = a;
    	a = b;
    	b = temp;
    }
    
    
    template <typename Type>
    void qSort( Type * array, int size )
    {
    	if ( size <= 1 )
    		return;
     
    	int middle = size / 2;
    	if ( array[middle] < array[0] )
    		Swap( array[middle], array[0] );
    	if ( array[size - 1] < array[0] )
    		Swap( array[size - 1], array[0] );
    	if ( array[size - 1] < array[middle] )
    		Swap( array[size - 1], array[middle] );
    
    	Type pivot = array[middle];
    	Swap( array[middle], array[size - 1] );
    
    
    	int i, j;
    
    	for ( i = 0, j = size - 1 ;; )
    	{
    		while ( array[++i] < pivot );
    		while ( pivot < array[--j] );
    		if ( i < j )
    			Swap( array[i], array[j] );
    		else break;
    	}
    
    	Swap( array[i], array[size - 1] );
    
    	qSort( &array[0], i - 1 );
    
    	qSort( &array[i + 1], ( size - (i + 1) ) );
    
    }
    I came up with a cool phrase to put down here, but i forgot it...

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,641
    It's a little late for me to throw my brain into it, so I'll just show you what I use.


    Code:
    template <class number>
    unsigned partition(number section[], unsigned start, unsigned finish, bool (*compare)(number, number) = greater) 
    {
     unsigned pivot = start;
     number value = section[pivot];
       for( unsigned index = start + 1; index < finish ; ++index )
         if( !compare( section[index], value ) )
           swap(section[index], section[++pivot]);
      swap(section[start], section[pivot]);
     return pivot;
    }
    
    template <class number>
    void quicksort(number section[], unsigned start, unsigned finish, bool (*compare)(number, number) = greater) 
    {
        if(start < finish) 
      {
       unsigned pivot = partition(section, start, finish, compare);
       quicksort(section, start, pivot, compare);
       quicksort(section, pivot + 1, finish, compare);
      }
     return;
    }
    
    template <class number>
    void quicksort(number section[], unsigned length, bool (*compare)(number, number) = greater) 
    {
     quicksort(section, 0, length, compare);
    }
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

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, 10:26 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

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