Help needed to perform quicksort on list

Hi,

I have a list of a datatype tag_t (similar to int). I need to sort this list using quicksort. This is what I tried.

I get the list to be sorted from a map and call quicksort on it.

Code:

std::list<tag_t> unsortedList = mpIter->second;
Quicksort(unsortedList, 0, unsortedList.size()-1);

My quicksort function is

Code:

void Quicksort(std::list < tag_t >  &tempList, int first, int last)
{
    int pivot;

    if (first < last)
    {
        pivot = Pivot(tempList, first, last);
        Quicksort(tempList, first, pivot - 1);
        Quicksort(tempList, pivot + 1, last);
    }
}

Code:

int Pivot(std::list < tag_t >  &tempList, int first, int last)
{
    int iStatus = ITK_ok;

    int p = first;
    list < tag_t > ::iterator listIter = tempList.begin();
    tag_t tempTag =  *listIter;
    tag_t firstTag =  *listIter;

    int iComparison = 0;

    for (int i = first + 1; i <= last; i++)
    {
        date_t date1;
        date_t date2;

/*the tag_t datatypes actually corresponds to date values, so I get the date values 
and compare them; if iComparison !=1 then date1 is earlier than date2. I am sorting 
the tags by ascending order of their dates*/


        iStatus = get_lastorder_date(tempTag, date1);
        SIEMENS_LOG_ERROR;

        iStatus = get_lastorder_date(*listIter, date2);
        SIEMENS_LOG_ERROR;

        iStatus = POM_compare_dates(date1, date2, &iComparison);
        SIEMENS_LOG_ERROR;

        if (iComparison != 1)
        {
            listIter++;
            p++;
            Swap(tempTag,  *listIter);
        }
    }

     Swap(*listIter, firstTag);

     return p;
}

Code:

void  Swap( tag_t &v1, tag_t &v2 )
{
    tag_t  tmpVal;

    tmpVal = v1;
    v1 = v2;
    v2 = tmpVal;
}

Even after calling the Quicksort function, the order of the unsortedList <tag_t> is unchanged.

Can someone please help me figure out the issue.

Thanks.

I do not think that quick sort on a doubly linked list is particularly good. You would not be able to use median of three or random pivot selection efficiently, and partitioning would not be so easy. Merge sort is likely to be better, but why implement a sorting algorithm for std::list yourself when std::list already has a sort() member function (or rather two, including the overload that sorts based on a predicate provided as an argument)?

In this case I find out if one tag_t datatype is less than or greater than another only after calling my POM_compare_dates api. Can I use the sort member function here too?

Originally Posted by lazyme

In this case I find out if one tag_t datatype is less than or greater than another only after calling my POM_compare_dates api. Can I use the sort member function here too?

Yes, but note that the predicate should be for a strictly "less than" comparison.

I am confused on how I can use the sort with an predicate in my case. Can you give me an example please?


Thanks

Given two tag_t, write a function (or function object) to return true if the first tag_t is "less than" the second tag_t.

I wrote a function

Code:

bool date_compare(tag_t tagObject1, tag_t tagObject2)
{
	int iStatus = ITK_ok;

	int iComparison = 0;

	date_t date1;
	date_t date2;
	
	iStatus = siemens_get_lastorder_date(tagObject1, date1);

	iStatus = siemens_get_lastorder_date(tagObject2, date2);

	iStatus = POM_compare_dates(date1, date2, &iComparison);

	if(iComparison == 1)
		return false;
	else
		return true;
}

and trying to call it as..

Code:

unsortedList.sort(date_compare);

But my compiler throws me an error

Code:

error C2660: 'std::list<_Ty>::sort' : function does not take 1 arguments

Also, is there a way I can use qsort in this case.

Originally Posted by lazyme

But my compiler throws me an error

That is a weird error message. Just to test, try to compile this program:

Code:

#include <list>

typedef int tag_t;

bool date_compare(tag_t tagObject1, tag_t tagObject2)
{
    return tagObject1 < tagObject2;
}

int main()
{
    std::list<tag_t> unsortedList;
    unsortedList.sort(date_compare);
}

Do you get any error messages?

Originally Posted by lazyme

Also, is there a way I can use qsort in this case.

No, qsort() does not play well with C++ standard library containers, with the exception of std::vector.

Yes. This compiles just fine.

What is the issue with my function then?

It compiled fine even after getting rid off

Code:

#include <list>

typedef int tag_t;

Edit : I found there was another int date_compare() function that was causing some problem. Got rid of that function and my code compiles fine now.

How does my code look?