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

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

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'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

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.

Wrap the member function call in a free function. With std::sort, a function object could be used instead of a free function.

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

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

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?

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.

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.

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

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.

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.