C++ Bubble sorting a Doubly Linked List

问题:

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;
}
}

回答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;
        }
    }
}

回答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.