Linked list and (alphabetic) bubble sorting

Question

I have got a problem with bubble sorting with a linked list. I have not found the bug in my simple code for few hours. Could you look at that?

int listSort(node_t ** _list)
{
     int size = listSize(_list);

     for(int i = 0; i < size; i++)
     {
          node_t *pointer = *_list;

          for(int j = 0 ; j < size - 1; j++)
          {
               if(strcmp(pointer->title, pointer->next->title) > 0)
                    listSwapWithNext(_list, j);

               pointer = pointer->next;
          }
     }

     return 0;
}

and here's swap function (but it seems to work fine, because I tested manually all boundary cases):

int listSwapWithNext(node_t **_list, size_t first)
{
     node_t *pointer = *_list;
     node_t *ptr_b;
     node_t *ptr_c;
     node_t *ptr_d;

     if(!first)
          ptr_b = pointer;

     for(size_t i = 0; pointer->next->next; i++, pointer = pointer->next)
     {
          if(i == first - 1 || first == 0)
          {
               if(first)
                    ptr_b = pointer->next;

               ptr_c = ptr_b->next;
               ptr_d = ptr_c->next;

               if(first)
                    pointer->next = ptr_c;
               else
                    *_list = ptr_c;

               ptr_c->next = ptr_b;
               ptr_b->next = ptr_d;

               break;
          }
     }

     return 0;     
}

It causes this crash (on line 229):

When I modified the condidition of inner loop in sort function to:

for(int j = 0; j < size - 1 && pointer->next; j++)

to prevent reading from bad address, I noticed strange thing. Inner loop somtimes run exactly one time less than it should.

Thank you!

EDIT: Here's modified version of sort function with prevent condition in inner loop and my debug indicators (made with printf()):

int listSort(node_t ** _list)
{
     int size = listSize(_list);
     int i;
     for(i = 0; i < size; i++)
     {
          node_t *pointer = *_list;
          int j;
          for(j = 0 ; j < size - 1 && pointer->next; j++)
          {
               if(strcmp(pointer->title, pointer->next->title) > 0)
                    listSwapWithNext(_list, j);

               printf("# %d %d\n", i, j);
               pointer = pointer->next;
          }
          printf("\n");
     }

     return 0;
}

Here's the result in console. Look, it doesn't do every cycle so it gaves bad sorting.

EDIT2: Here's the essention of the problem. http://pastebin.com/e5K6C1A2

Still cant resolve this issue.

Answer 1

pointer = pointer->next is not correct in the case where a swap is made. If you made a swap, pointer should remain pointer because it has been moved forward by one element already.

Edit: I mean do this:

if(strcmp(pointer->title, pointer->next->title) > 0)
    listSwapWithNext(_list, j);
else
    pointer = pointer->next;

Answer 2

Based on what you have said I believe I can help you identify a few problems in your code. I believe that the issues that you are describing are caused by the first block of code that you posted, specifically this part.

 for(int i = 0; i < size; i++)
     {
          node_t *pointer = *_list;

          for(int j = 0 ; j < size - 1; j++)
          {
               if(strcmp(pointer->title, pointer->next->title) > 0)
                    listSwapWithNext(_list, j);

               pointer = pointer->next;
          }

The problem is being thrown by this line:

if(strcmp(pointer->title, pointer->next->title) > 0)

because of how the inner loop is constructed here:

for(int j = 0 ; j < size - 1; j++)

So you are accounting for the fact that because we are swapping we need 1 less than the total size of the list. The problem however is that this is causing you to try to dereference a null pointer on the last run through it. A node in a linked list contains a pointer to some data and a pointer to the next object. So lets imagine what happens the second to last time this for loop executes. It does your swap if strcmp is true then it advances the pointer to reference the next element in the linked list. Here is where you go wrong. Because you have done that when we execute the loop again, this line:

if(strcmp(pointer->title, pointer->next->title) > 0) 

specifically this part of it: pointer->next->title will fail because the current object is the last element in the linked list. For this reason its next points to NULL and you are trying to get the title object of a NULL element, which doesn't exist.

Now lets look at your modified code.

int listSort(node_t ** _list)
{
     int size = listSize(_list);
     int i;
     for(i = 0; i < size; i++)
     {
          node_t *pointer = *_list;
          int j;
          for(j = 0 ; j < size - 1 && pointer->next; j++)
          {
               if(strcmp(pointer->title, pointer->next->title) > 0)
                    listSwapWithNext(_list, j);

               printf("# %d %d\n", i, j);
               pointer = pointer->next;
          }
          printf("\n");
     }

     return 0;
}

you don't suffer from the same error but you get incorrect results. This isn't caused by the sorting function, again this is caused by the construction of the for loop here:

for(j = 0 ; j < size - 1 && pointer->next; j++)

A for loop will execute as long as the specified condition is true. Again lets imagine the second to last execution. We are within our size bounds so the first condition is true and another element exists after this so the second condition is also true. The loop runs and advances the pointer to the next element. Now we are still within our size constraints so thats true but there is no more elements in the list after this so pointer->next is NULL. This means that the loop won't run and thus won't sort all of the data giving you bad results.