Sorting a Doubly Linked List C++ Question

Question

Trying to do it through a loop that traverses through the list.

In the loop im feeding the head node into a sorting function that I have defined and then im using strcmp to find out if which name in the node should come first.

Its not working because writing the names too early.

Im comparing them all linearly by going down the list one node at a time and not going back to see if the first should come before the last. That part explained would be helpful.

The two functions that are most important to me now are defined as follows: I have tried my best to do what I think is right for the sorting function.

void list::displayByName(ostream& out) const
{
    list *ListPtr = NULL;
    node *current_node = headByName;
    winery *wine_t = new winery(); 
    // winery is another class object type
    // im allocating it to prevent a crash when I call it.

    while ( current_node != NULL )
    {
        *(wine_t) = current_node->item;
        wine_t = ListPtr->sort( current_node );
        out << wine_t << endl;
        current_node = current_node->nextByName;
    }
    delete wine_t;
}

winery * const list::sort( node * current_node ) const
{
    // current_node is the first node.
    const char *SecondName = NULL, *FirstName  = NULL;
    winery *wine_t   = new winery();

    if ( current_node != NULL )
    {
        SecondName   = current_node->item.getName();      
        current_node = current_node->nextByName;
        FirstName    = current_node->item.getName();
    }

    if ( strcmp( FirstName, SecondName ) == -1 )
    {
        *(wine_t)  = current_node->item;
        FirstName  = NULL;
        SecondName = NULL;
        return wine_t;
    }
    else if ( strcmp( FirstName, SecondName ) == 1 )
    {
        *(wine_t) = current_node->item;
        FirstName = NULL;
        SecondName = NULL;
        return wine_t;
    }
    else return wine_t;// then the strings are equal

    FirstName  = NULL;
    SecondName = NULL;
    return wine_t;
}

And I started to develop my nodes here:

void list::insert(const winery& winery)
{
    node *current_node = new node( winery );

    if ( headByName == NULL )
    {
        headByName   = current_node;
        headByRating = current_node;
        tail         = headByName;
        current_node->prev = current_node;
    }
    else
    {
        current_node->prev = tail;
        tail->nextByName   = current_node;
    }

    tail = current_node;
    current_node = NULL;
}

I think its correct in that function above. Could I possible get a way with sorting it their?

Below are my varaibles that I am working with:

public list
{
         ...
    void insert(const winery& winery);
    void displayByName(ostream& out) const;
}
private:
    struct node
    {
        node(const winery& winery);  // constructor
        winery item;
        node * prev;
        node * nextByName;
        node * nextByRating;
    };

    winery * const sort(node*) const;
    node * headByName;
    node * headByRating;
    node * tail;
};

Any help is appreciated. Thanks very much =)

Answer 1

I wouldn't bother to write my own sort function. I'd just use qsort. Since it's interface is c and not c++, to use it you just build an array of object pointers, then call qsort on it with your own comparator function. Then rebuild the linked list from the newly sorted array of object pointers.

Answer 2

Before I even get to the question asked, I observe some problems you probably want to address:

• Your nodes have two different kinds of next's, but only one kind of prev. Is that really what you want, and if so, which next is paired with the prev?
• The method you have named sort doesn't sort, but acts as a comparison.
• You don't appear to have implemented an actual sort (or at least you haven't exhibited it here).
• There is no need for the repetitive setting of FirstName and SecondName back to NULL in sort. They are local variables and simple disappear when the method returns.
• There is no need to do two strcmp's in sort. Either cache the result of the first one ( int cmp=strcmp(...); ) or use a switch on the value returned by strcmp`.

To sort a double linked array I would I would suggest one of:

1. Using a standard container that supports std::sort if this is allowed (but I'm guessing that this is homework, so probably not). I believe that std::list qualifies.
2. Sorting at insertion time if the sort order will never change
3. Implementing a partition sort (i.e. quicksort), which will work very nicely on this kind of structure (but the usual example code is given on arrays, so you will have to understand what is being done and why before the right way to implement it on linked lists becomes apparent).

Answer 3

From what I understand, you want list::sort to find the least node in the list which is greater than the input.

To do this, you need to iterate through all the elements and keep the current least-but-greater node found.

Something like this:

node * const list::sort( node * given_node ) const
{
    if ( given_node == NULL )
    {
        return NULL;
    }

    // Smallest node found which is greater than given_node.
    node * least_found_node = NULL;

    // Node we are looking at right now.
    node * current_node = given_node->nextByName;

    // Go through all nodes.
    while ( current_node && current_node != given_node )
    {
        // Is this node bigger than the given node?
        if ( strcmp( current_node->item.getName(), given_node->item.getName() ) < 0 )
        {
            // Is this node smaller than the smallest node we know of?
            if ( least_found_node == NULL ||
               ((strcmp( current_node->item.getName(), least_found_node->item.getName() ) > 0) )
            {
                // We found a better node.
                least_found_node = current_node;
            }
        }

        current_node = current_node->nextByName;
    }

    return least_found_node;
}

Now change your display function to use it like this:

void list::displayByName(ostream& out) const
{
    // Find first node initially.
    node * current_node = sort( NULL );

    while ( current_node != NULL )
    {
        // Print node.
        out << current_node->item.getName();

        // Find next node in sorted output.
        current_node = sort( current_node );
    }
}

This part keeps calling sort until sort returns NULL. The first call to sort is with NULL so the lowest item is found (that is, the first in the sorted list). sort returns NULL if there are no more nodes larger than current_node, thus terminating the loop.

Answer 4

If you are looking for an efficient in-place sort algorithm for linked lists, check out this one ... I've found it to be quite fast.

Answer 5

Why isn't using std::list (the STL's doubly-linked list) and its associated sort function appropriate here? If you defined an operator< for your list items, it will Just Work and you won't have to write a whole bunch of code just to have a list and sort it.