Quick Sort

This is a discussion on Quick Sort within the C++ Programming forums, part of the General Programming Boards category; here is my sort algorithm: Code: // ---------------------------------------------------------------- // Name: QuickSort // Description: quicksorts the array // Arguments: p_array: the ...

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    54

    Quick Sort

    here is my sort algorithm:

    Code:
    // ----------------------------------------------------------------
    //  Name:           QuickSort
    //  Description:    quicksorts the array
    //  Arguments:      p_array: the array to sort
    //                  p_first: first index of the segment to sort
    //                  p_size: size of the segment
    //                  p_compare: comparison function
    //  Return Value:   None
    // ----------------------------------------------------------------
    template<class DataType>
    void QuickSort( vector<DataType>& p_array, 
                    int p_first, 
                    int p_size, 
                    int (*p_compare)(DataType, DataType) )
    {
        DataType pivot;
        int last = p_first + p_size - 1;    // index of the last cell
        int lower = p_first;                // index of the lower cell
        int higher = last;                  // index of the upper cell
        int mid;                            // index of the median value
    
        // if the size of the array to sort is greater than 1, then sort it.
        if( p_size > 1 )
        {
            // find the index of the median value, and set that as the pivot.
            mid = FindMedianOfThree( p_array, p_first, p_size, p_compare );
            pivot = p_array[mid];
    
            // move the first value in the array into the place where the pivot was
            p_array[mid] = p_array[p_first];
    
            // while the lower index is lower than the higher index
            while( lower < higher )
            {
                // iterate downwards until a value lower than the pivot is found
                while( p_compare( pivot, p_array[higher] ) < 0 && lower < higher )
                    higher--;
    
                // if the previous loop found a value lower than the pivot, 
                // higher will not equal lower.
                if( higher != lower ) 
                {
                    // so move the value of the higher index into the lower index 
                    // (which is empty), and move the lower index up.
                    p_array[lower] = p_array[higher];
                    lower++;
                }
    
                // now iterate upwards until a value greater than the pivot is found
                while( p_compare( pivot, p_array[lower] ) > 0 && lower < higher )
                    lower++;
    
                // if the previous loop found a value greater than the pivot,
                // higher will not equal lower
                if( higher != lower )
                {
                    // move the value at the lower index into the higher index,
                    // (which is empty), and move the higher index down.
                    p_array[higher] = p_array[lower];
                    higher--;
                }
            }
    
            // at the end of the main loop, the lower index will be empty, so
            // put the pivot in there.
            p_array[lower] = pivot;
    
            // recursively quicksort the left half
            QuickSort( p_array, p_first, lower - p_first, p_compare );
    
            // recursively quicksort the right half.
            QuickSort( p_array, lower + 1, last - lower, p_compare );
        }
    }

    now i got this working before with one of my classes

    before the class i decared this function:

    Code:
    //use quick sort to keep windows drawn in the proper order
    // compare the y values only.
    int CompareZ( cBaseWindow* l, cBaseWindow* r )
    {
    	if (l->getZ() == r->getZ() )
    	{
    		if( l->getZ() < r->getZ() )
    			return 1;
    		if( l->getZ() > r->getZ() )
    			return -1;
    	}
    	if( l->getZ() < r->getZ() )
            return -1;
        if( l->getZ() > r->getZ() )
            return 1;
        return 0;
    }
    then a member of my class uses the QuickSort (look at the bottom bit):

    Code:
    void cGUIManager::GUIMouseDown(float x, float y)
    {
    	int tmpZ = WindowList.size()+1;
    
    	
    	
    	for (unsigned int iloop=0;iloop<WindowList.size();iloop++)
    	{
    		if (WindowList[iloop]->MouseTest(x,y))
    		{
    			if(WindowList[iloop]->getZ()<tmpZ && WindowList[iloop]->getVisible()==true && WindowList[iloop]->getEnabled())
                { tmpZ=WindowList[iloop]->getZ() ;
    		      ClearFocus();
    		      WindowList[iloop]->SetFocus();
    		      WindowList[iloop]->MouseDown(x,y);			
                }
    		}
    				
    	}	
    	
    	
    	if (tmpZ > 0 && tmpZ<WindowList.size()+1)
    	{ //Brought a window to the front so reorder the others down one
    		for (unsigned int iloop=0;iloop<WindowList.size();iloop++)
    		{
    			WindowList[iloop]->Reorder(tmpZ);
    		}
    		//Resort the List for the New Order
    		QuickSort(WindowList,0,WindowList.size(),CompareZ);
    	}
    };
    and this all worked fine,

    then i decided that i wanted to have the CompareZ function as a member of the class.

    so i did this:

    Code:
    int cGUIManager::CompareZ( cBaseWindow* l, cBaseWindow* r )
    {
    	if (l->getZ() == r->getZ() )
    	{
    		if( l->getZ() < r->getZ() )
    			return 1;
    		if( l->getZ() > r->getZ() )
    			return -1;
    	}
    	if( l->getZ() < r->getZ() )
            return -1;
        if( l->getZ() > r->getZ() )
            return 1;
        return 0;
    }
    and this:

    Code:
    void cGUIManager::GUIMouseDown(float x, float y)
    {
    	int tmpZ = WindowList.size()+1;
    
    	
    	
    	for (unsigned int iloop=0;iloop<WindowList.size();iloop++)
    	{
    		if (WindowList[iloop]->MouseTest(x,y))
    		{
    			if(WindowList[iloop]->getZ()<tmpZ && WindowList[iloop]->getVisible()==true && WindowList[iloop]->getEnabled())
                { tmpZ=WindowList[iloop]->getZ() ;
    		      ClearFocus();
    		      WindowList[iloop]->SetFocus();
    		      WindowList[iloop]->MouseDown(x,y);			
                }
    		}
    				
    	}	
    	
    	
    	if (tmpZ > 0 && tmpZ<WindowList.size()+1)
    	{ //Brought a window to the front so reorder the others down one
    		for (unsigned int iloop=0;iloop<WindowList.size();iloop++)
    		{
    			WindowList[iloop]->Reorder(tmpZ);
    		}
    		//Resort the List for the New Order
    		QuickSort(WindowList,0,WindowList.size(),cGUIManager::CompareZ);
    	}
    };
    but it did not work, i got the following error:
    Code:
     no matching function for call to `QuickSort(std::vector<cBaseWindow*, std::allocator<cBaseWindow*> >&, int, size_t, <unknown type>)'
    it seems the quick sort algorithm did not like accepting cGUIManager::CompareZ as a comparision function to use, but i am not sure why, or what i can to to make it accept the classes member function..

    any help will be greatly appriciated

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I thought one of the "nice" things with C++ and templates is that you can define an operator< or operator> that would compare two items and return a bool - and thus be able to replace:
    Code:
               while( p_compare( pivot, p_array[lower] ) > 0 && lower < higher )
    with
    Code:
               while(  pivot > p_array[lower]  && lower < higher )
    Am I missing something here?

    --
    Mats

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Firstly, did you write your own quicksort, because you didn't think std::sort can't handle your class?

    If you are sure you want to do it this way you'll need to keep in mind that using the function pointer of a member function is different. For one thing they have the hidden this parameter (static members don't have it).

    It also seems that you have done a lot of extra work to provide the strict ordering (return values -1, 0, 1 from compare function). To quicksort stuff you'll only need weak ordering (bool - is left smaller than right). (This is what standard algorithms use.)

    ---------
    Anyway, the best thing to do is to provide a C++ standard compatible compare function/functor for the objects you want to sort and use std::sort.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    54
    i'm not sure, i did not write that quick sort algorith, i am mearly try to use it,
    i am having trouble calling the quicksort function if my p_compare: comparison function is a member of a class

  5. #5
    Registered User
    Join Date
    Jan 2007
    Posts
    54
    i will have a look into std::sort however i would like to know why i get the error when i try to pass a member function, and how i can correctly pass the memeber function.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    Wrap the member function call in a free function. With std::sort, a function object could be used instead of a free function.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    54
    so it's not possible to pass it a memeber function directly?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    so it's not possible to pass it a memeber function directly?
    Yes, since it is designed to accept a free function (or for std::sort, a free function or function object).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Jan 2007
    Posts
    54
    so that's why i get the

    no matching function for call to `QuickSort(std::vector<cBaseWindow*, std::allocator<cBaseWindow*> >&, int, size_t, <unknown type>)'

    error?

    also would it be possible to rewrite that QuickSort function to accept a member function?
    Last edited by e66n06; 08-20-2007 at 01:52 PM.

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by e66n06 View Post
    so it's not possible to pass it a memeber function directly?
    A non-static member function, by definition, is associated with a specific instance of an object. So no, you can't just pass a pointer to a member function without also passing a pointer to the relevant object.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A member function doesn't apparently match the prototype of the function pointer (or however it is called).

    The idea of using a plain member function here is flawed anyway: you only work with two object pointers, and you don't use the this pointer that is passed to each non-static member function explicitly. If you made the compare function static and return a bool for weak ordering (is-smaller-than) then std::sort would probably work for you.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by anon View Post
    A member function doesn't apparently match the prototype of the function pointer (or however it is called).
    Yes, like brewbuck says. Essentially it boils down to "object::func(int a, float b)" can be rewritten as "func(object *this, int a, float b)" - this function is obviously not compatible with a prototype of "proto(int a, float b)", since it's got another argument added - albeit a hidden argument.

    --
    Mats

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by e66n06 View Post
    Code:
    int cGUIManager::CompareZ( cBaseWindow* l, cBaseWindow* r )
    {
    	if (l->getZ() == r->getZ() )
    	{
    		if( l->getZ() < r->getZ() )
    			return 1;
    		if( l->getZ() > r->getZ() )
    			return -1;
    	}
    	if( l->getZ() < r->getZ() )
            return -1;
        if( l->getZ() > r->getZ() )
            return 1;
        return 0;
    }
    That's a seriously overkill function there. You first check if l->getZ() and r->getZ() are equal, and if the ARE, you then ask if they aren't again - twice! In that case those will of course fail, and then you do the same test twice again outside of the if-statement, both of which will also fail. Talk about redundant code! The whole bracketed if-statement can be deleted entirely.
    You should read over your code after you write it so that you catch daft things like that. Just like you'd proofread a novel.

    Secondly, all you're missing to use this function is the 'static' keyword.

    Lastly, try not to mix tabs and spaces.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    bool cGUIManager::CompareZ( const cBaseWindow* l, const cBaseWindow* r )
    {
        return l->getZ() < r->getZ();
    }
    Here's an even simpler compare function that would get the job done. In the sort function you are only using is-less-than and is-larger-than and not is-equal-to, and you don't need a is-larger-than case because you can simply switch around the parameters. So the usage becomes:

    Code:
     // while( p_compare( pivot, p_array[higher] ) < 0 && lower < higher )
            while (p_compare(pivot, p_array[higher]) && lower < higher)
                    higher--;
    
                ...
    
                // now iterate upwards until a value greater than the pivot is found
                //while( p_compare( pivot, p_array[lower] ) > 0 && lower < higher )
            while (p_compare(p_array[lower], pivot) && lower < higher)
                    lower++;
    It also seems to me that the sort algorithm may use too many lower-higher comparisons. For example in these loops the algorithm itself should guarantee that only the first condition is enough to make it stop at the right place (although I might be wrong here).

    Anyway, the above function (if you make it static or - I'd prefer - non-member, as it is probably using only a public getter) should be fine for std::sort.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

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, 04:51 PM
  2. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 09:51 AM
  3. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 09:06 AM
  4. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 09:34 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

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