Thread: Quick Sort

  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
    28,413
    Wrap the member function call in a free function. With std::sort, a function object could be used instead of a free function.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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
    28,413
    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).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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,318
    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, 05:51 PM
  2. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 10:51 AM
  3. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 10:06 AM
  4. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 10:34 PM
  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