1. ## 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. 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. 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.

4. 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. 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. Wrap the member function call in a free function. With std::sort, a function object could be used instead of a free function.

7. so it's not possible to pass it a memeber function directly?

8. 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).

9. 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?

10. 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.

11. 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.

12. 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

13. 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.

14. 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.