CODEWITHSUNDEEP
csortinglinked-list
Mathias
Mathias

Reputation: 605

Bubble sorting a linked list in C

I have created a linked list of 5 nodes of type:

typedef struct node
{
    int i;
    struct node* link;
}node;

node* head = NULL;

When printing out, this gives:

4 3 2 1 0

The head pointer is set to point at 4. I have then written a function to bubble sort the linked list as follows:

void sort(void)
{
     node* cur = head;
     node* next = cur->link;
     node* prev = NULL;

     while(cur->i > next->i)
     {
        printf("cur is greater than next\n");

        while(prev != head)
        {
          cur->link = next->link;
          next->link = cur;
          head = next;
          next = cur->link;
          prev = head;
        }
        while(next != NULL)
        {
          prev->link = next; 
          cur->link = next->link;
          next->link = cur;
          prev = next;
          next = cur->link;
        }
        printf("second while loop exited\n");

        for (node* ptr = head; ptr != NULL; ptr = ptr->link)
        {
           printf("%d", ptr->i);
        }

        cur = head;
        next = cur->link;

      } 
}

There are various printf statements to check that the program is working. What I find is that after the first run-through, 4 is successfully bubbled up as follows:

3 2 1 0 4

However, after re-setting the cur pointer to 3 and next to 2, the next run-through provides the following:

2 1 0 4 3

Ultimately, we finish with 

0 4 3 2 1

So as can be seen "3", "2" and "1" are being bubbled up too far. I have tried various conditonals in place of the third while loop to correct this but in the majority of cases this leads to seg faults. Of course, the other thing here is that my logic could be completely wrong and there may be a better way to implement this. Could you get away with just swapping the contents of nodes and not pointers themselves? Any help would be much appreciated. Thanks in advance

Upvotes: 2

Views: 2030

Answers (2)

CiaPan
CiaPan

Reputation: 9570

Ordinary bubble-sort implementations for sorting arrays make use of the direct addressing and a known size of the array: they naturally use indices, that is ordinal numbers of items, so they can easily shrink the area sorted as the work progresses, because they know how many items are already on their final places.

A linked list is processed purely sequentially, so it doesn't allow such simple optimization without adding artificial 'index', incremented along the list iteration. That's why it's easiest to iterate always through the whole list and terminate when no more items were swapped, hence the list is sorted:

void sort(void)
{
    int swapped = 1;

    while(swapped)
    {
        node **prev = &head, *curr, *next;

        swapped = 0;
        for(curr = head; curr; prev = & curr->link, curr = curr->link)
        {
            next = curr->link;

            if(next && curr->i > next->i)
            {
                curr->link = next->link;
                next->link = curr;
                *prev = next;

                swapped = 1;
            }
        }
    }
}

EDIT – some explanations in reply to questions in Matthew2015 comments.

Logical conditions in C expect a numeric or pointer expression which are considered 'true' if they are different from zero or different from NULL, respectively. That means while(swapped) is essentially equivalent to while(swapped != 0) and next && ... is equivalent to next != NULL && .... The condition in while(swapped != 0) means the loop will terminate when some execution of internal for does not set swapped to 1, which happens when no item in the list is greater than its successor – that is, when the list is sorted.

The for loop condition expression is curr alone, equivalent to curr != NULL. That makes the for loop iterate along the list until there is no 'current' node.

The node **prev variable points to a pointer, which points to the current node. When the 'current' and the 'next' node need to be swapped, then the 'previous' link should no longer point to the 'current' node but to the 'next' node instead. Of course one might keep the pointer to the 'previous node' and assign a new value to the (previous node)->link — but that would not work in case of the first node in a list, which has no 'previous node' but is pointed to by the head variable. One must use additional condition to verify if the current node is the first node to resolve this inconsistency. Having a pointer to pointer, which originally points to head and then to 'previous node'.link makes the whole code much simpler, shorter and also a bit faster.

Upvotes: 3

mw215
mw215

Reputation: 323

I would look at the third while

    while(next != NULL)
    {
      prev->link = next; 
      cur->link = next->link;
      next->link = cur;
      prev = next;
      next = cur->link;
    }

Here you're always moving elements without testing whether they have to be moved - i.e. cur->i > next->i.

By the way, if it's guard is true, the second while gets executed only once and so it's the same as an if so I would use an if, at least for clarity reasons.

Upvotes: 1

Related Questions