# Quick Sort

• 08-20-2007
e66n06
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 :D
• 08-20-2007
matsp
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
• 08-20-2007
anon
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.
• 08-20-2007
e66n06
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
• 08-20-2007
e66n06
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.
• 08-20-2007
laserlight
Wrap the member function call in a free function. With std::sort, a function object could be used instead of a free function.
• 08-20-2007
e66n06
so it's not possible to pass it a memeber function directly?
• 08-20-2007
laserlight
Quote:

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).
• 08-20-2007
e66n06
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?
• 08-20-2007
brewbuck
Quote:

Originally Posted by e66n06
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.
• 08-20-2007
anon
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.
• 08-20-2007
matsp
Quote:

Originally Posted by anon
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
• 08-21-2007
iMalc
Quote:

Originally Posted by e66n06
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.
• 08-21-2007
anon
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.