C++ Bubble sorting a Doubly Linked List

Question

I know bubble sort is probably not the fastest way to do this but its acceptable. i'm just having trouble with adjusting the algorithm to double link lists from arrays.

My double linked lists have a type int and a type string to hold a number and a word. My list was sorted with an insertion sort that I wrote to sort alphabetically, now I need to reorder my double linked list numerically, greatest to least.

My trouble spot is how to run this loop so that it is properly sorted thoroughly and not just one time.

here's what i've managed to get down so far:

void DblLinkedList::ReorderListNumeric()
{
dummy = new Node();
temphead = head;
temp = head->next;

while(tempTwo->next != NULL)
{
    if(temp->wordCount < tempTwo->wordCount)
    {               
        dummy->word = tempTwo->word;
        dummy->wordCount = tempTwo->wordCount;

        tempTwo->word = temp->word;
        tempTwo->wordCount = temp->wordCount;

        temp->word = dummy->word;
        temp->wordCount = dummy->wordCount;
    }
    temp = tempTwo;
    tempTwo = tempTwo->next;
}
}

Solution 1

My trouble spot is how to run this loop so that it is properly sorted thoroughly and not just one time.

If you already have a loop that will successfully do one pass and swap is okay, the usual way to do multiple passes relatively efficiently is:

set swapped = true
while swapped:
    set swapped = false
    do your one pass, setting swapped to true whenever you swap

This avoids the naive n² solution that beginners will invariably start with.

And that's it really.

You set swapped to true so that you initially enter the list then set it to false immediately, inside the loop.

Your single pass will set swapped only if a swap takes place. If no swap takes place in your pass, then the list is sorted and you exit the loop.

If any swap takes place, the swapped flag is set and you will need to run another pass. This is because the swap could be at the end of the list and invalidate the order earlier on, such as:

Initial: 1   2   3   4   6   7   5
  Pass1: 1   2   3   4   6   5<=>7 (swap)
  Pass2: 1   2   3   4   5<=>6   7 (swap)
  Pass3: 1   2   3   4   5   6   7 (no swap, so exit loop)

So, assuming your code is correct, start with something like:

void DblLinkedList::ReorderListNumeric() {
    Node *ptr, *dummy = new Node();

    // Zero or one element, no sort required.

    if (head == NULL) return;
    if (head->next == NULL) return;

    // Force initial entry.

    int swapped = 1;
    while (swapped) {
        // Flag as last time, then do one pass.

        swapped = 0;

        ptr = head;
        while (ptr->next != NULL) {
            if (ptr->wordCount < ptr->next->wordCount) {
                // Swapping, need another pass.

                swapped = 1;

                dummy->word = ptr->word;
                ptr->word = ptr->next->word;
                ptr->next->word = dummy->word;

                dummy->wordCount = ptr->wordCount;
                ptr->wordCount = ptr->next->wordCount;
                ptr->next->wordCount = dummy->wordCount;
            }
            ptr = ptr->next;
        }
    }
}

Solution 2

Use 2 loops to sort the list thoroughly ( I am not considering the efficiency here as thats not important to you at the moment). So iterate the list with 2 pointers as you would do with arrays -

void DblLinkedList::ReorderListNumeric()
{
    NODE* temphead = NULL; // assuming your list is made of NODEs
    NODE* temp = NULL;

    for(temphead = head; temphead && temphead->next != NULL; ++ temphead)
    {
        for(temp = temphead->next; temp && temp->next != NULL; ++temp)
        {
            if(temphead->wordCount < temp->wordCount)
            {
                std::string dummyWord = temp->word;
                int dummyCount = temp->wordCount;

                temp->word = temphead->word;
                temp->wordCount = temphead->wordCount;

                temphead->word = dummyWord;
                temphead->wordCount = dummyCount;
            }
        }
    }
}

BTW, Why do want to create a dummy node to swap, when all you want is to swap the values.

Comments

[vrdhn]

Make a function swap(i,j) so that you can unit test it.

[Reinderien]

Just to cover all of our bases: I'll assume that you already know of the existing linked list implementations and the built-in sorting function in the C++ STL, and that your current work is for some hobby or school assignment.

[SingleNegationElimination]

under certain conditions, bubble sort is often optimal. Don't discount it just because of its asymptotic performance.

[paxdiablo]

Yes, there are places where bubble sort is acceptable. I actually use it to sort transactions in my company records (a simple OOo spreadsheet for doing txn list, balance sheet and P&L). Since this is mostly sorted already (other than 3 or 4 transactions at the end), it's usually blindingly fast. And, no, I can't use the standard sorting because a transaction crosses multiple rows, with the sort key only on the first, and I have to keep it together. By doing passes in alternating directions, it's also good for adding a txn that needs to go up the top somewhere.

[sje397]

Another optimisation is to take advantage of the knowledge that after the first pass, the last item is correct - you don't have to pass over the entire list with successive passes.

[paxdiablo]

That's not a bad idea. You need to figure out the length of the list but you can do that on the first pass, to be decremented and used on subsequent passes. But someone using bubble sort is probably not too worried about efficiency :-)

[Matt Swezey]

Thank you so much for taking your time out and explaining what is going on there. Learned another today! Worked amazingly after fiddling with my code for 10 mins!

[Matt Swezey]

Learned another new thing today*!!