CODEWITHSUNDEEP
cbubble-sort
Jerry Singh
Jerry Singh

Reputation: 71

swapping nodes for a bubble sort doubly linked list C

Welp I'm back. I am now trying to do a bubble sort with a node swap. There is a problem in my algorithm that i cannot determine. When I remove the bool condition to determine if the list is sorted, the program produces some output, indicating the loop condition is failing to a problem in the algorithm. i have diagrammed out what happens on paper, with each pointer as it is reassigned. I envisioned nodes a b c d, where b and c are swapped. the sort function is below. i have made notes for every action in an attempt to figure what i am doing wrong. no dice, any guidance would be greatly appreciated, thank you.

void sortList(void)
{
    struct Node *before, *after;
    struct Node * temp;

    bool sorted = false;

    while (sorted == false)
    {
        //test completion
        sorted = true;  //if this isn't changed by the below statement the list is sorted
        temp = head;    //reinitializes where there list sorts from
        while (temp->next != NULL)  //stops at the end of the list
        {
            if (temp->data > temp->next->data)
            {
                //test the value of the nodes to see if they need a sort

                before = temp->prev;    //"back" pointer for subject (b)
                after = temp->next; //"forward" pointer for subject
                if (before != NULL)
                {
                    before->next = after;   //covers swap being made at beginning
                }
                temp->next = after->next;   //points to after next
                after->next->prev = temp;   //sets prev pointer for "d"
                temp->prev = after; //points to what after pointed
                after->next = temp; //places node after next one
                after->prev = before;   //ditto

                sorted = false; //flagged, the list is not sorted
            }
            temp = temp->next;  //moves through the list

        }
    }
}

Upvotes: 0

Views: 708

Answers (1)

Ian Abbott
Ian Abbott

Reputation: 17503

There are three main problems in the original sortList function:

  1. It doesn't update head when moving the first node in the list. (Fix: add an else part to update head.)
  2. after->next->prev dereferences a null pointer at the end of the list. (Fix: check after->next != NULL first.)
  3. temp = temp->next dereferences a null pointer at the end of the list and skips a position when not at the end of the list. The code that swaps the temp node with the following node already advances temp one position through the list, so it should not be done again. (Fix: move temp = temp->next; into an else part executed only when the temp node does not need to be swapped.)

Here is an updated version of sortList() with the changes marked:

void sortList(void)
{
    struct Node *before, *after;
    struct Node * temp;

    bool sorted = false;

    while (sorted == false)
    {
        //test completion
        sorted = true;  //if this isn't changed by the below statement the list is sorted
        temp = head;    //reinitializes where there list sorts from
        while (temp->next != NULL)  //stops at the end of the list
        {
            if (temp->data > temp->next->data)
            {
                //test the value of the nodes to see if they need a sort

                before = temp->prev;    //"back" pointer for subject (b)
                after = temp->next; //"forward" pointer for subject
                if (before != NULL)
                {
                    // temp is not at beginning of list
                    before->next = after;
                }
                else
                {
                    // *** Fix 1 ***
                    // temp is at beginning of list
                    head = after;
                }
                temp->next = after->next;   //points to after next
                if (after->next != NULL) // *** Fix 2 ***
                {
                    after->next->prev = temp;   //sets prev pointer for "d"
                }
                temp->prev = after; //points to what after pointed
                after->next = temp; //places node after next one
                after->prev = before;   //ditto

                sorted = false; //flagged, the list is not sorted
            }
            else // *** Fix 3 ***
            {
                temp = temp->next;  //moves through the list
            }

        }
    }
}

EDIT

The above version of sortList fails when head is NULL (an empty list) due to temp->next dereferencing a null pointer. One way to fix it is to mark an empty list as already sorted by changing the initialization of sorted as follows:

    bool sorted = (head == NULL);

The amount of work done by sortList can be halved (approximately) by reducing the number of iterations of the inner loop by one after for each iteration of the outer loop. This can be done as follows:

  1. Add a new variable done to mark the start of the already sorted portion at the end of the list. Initialize it to NULL near the top of the function (before the outer loop):
    struct Node *done = NULL;
  1. Change the condition for the inner loop to terminate at the end of the unsorted portion of the list:
    while (sorted == false)
    {
        //test completion
        sorted = true;  //if this isn't changed by the below statement the list is sorted
        temp = head;    //reinitializes where there list sorts from
        while (temp->next != done) // stops at the sorted portion of the list
        {
  1. When the inner loop has terminated (at the end of the outer loop), the temp node and everything beyond it is now sorted, so make done point to this node:
        }
        done = temp;    // everything from here is already sorted
    }
}

Upvotes: 1

Related Questions