Thread: Help needed to perform quicksort on list

  1. #1
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53

    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.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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)?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    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?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    I am confused on how I can use the sort with an predicate in my case. Can you give me an example please?


    Thanks

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    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.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote 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?

    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    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?
    Last edited by lazyme; 05-15-2009 at 02:43 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. urgent help please...
    By peter_hii in forum C++ Programming
    Replies: 11
    Last Post: 10-30-2006, 06:37 AM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  4. Linked List help needed
    By EDL in forum C++ Programming
    Replies: 3
    Last Post: 05-30-2002, 10:01 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM