Thread: 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