sorting a singly linked list

[jou00jou]

Hello,
I am trying to sort a singly linked list for the following typedef
typedef struct message {
int messageId;
char * messageText;
struct message * next;
} message;
I have successfully implemented add, delete, print, and search functions for the linked list but I am not sure why I am stuck with this one.


I posted my code below. I get a BUS error in the second iteration of the while loop. I am quite new to linked list so I will appreciate any explanation.

Thank you

    if(first != NULL && first->next != NULL) /* less than two nodes */
    {        
        message *a = first;
        message *b = first->next;
        message *beforeA =  NULL;
 
        while(b != NULL)
        {
            if(a->messageId > b->messageId)
            {
                a->next = b->next;
                b->next = a;
                if(a == first && beforeA == NULL)
                {
                    first = b;
                    beforeA = first;
                }
                else if (beforeA != NULL)
                {
                    beforeA->next = b;
                }
                /* Move to the next couple of nodes */
                b = a->next;
                beforeA = beforeA->next;
            }else if (a->messageId < b->messageId)
            {
                                beforeA = a;
                a = a->next;
                b = b->next;
            }
        }
    }
 

[Banfa]

Although that is not how I might write the code I am finding it hard to see any error in it. Is it possible that the data in the list has been de-allocated somehow before sorting. Otherwise I think we are going to need to see the input data to the function in order to be able to diagnose the problem.

[jou00jou]

I don't think this has to do with the input. I guess there is something wrong with the implementation. But here is a sample input.
4 sample text
1 another sample text
8 one more sample
6 more sample

How would you write the code?

Thank you for your reply

[Banfa]

I think that the logic is wrong because in the case of

a->messageId > b->messageId is TRUE
AND
a == first is TRUE
AND
beforeA == NULL is TRUE

as would be the case in the data you have provided at the end of the first iteration beforeA == A I think (checked on paper), you could verify this using a debugger.

I assume beforeA is actually meant to point to the entry before a and not the same entry as a so the logic has gone wrong.


If I wrote this I would not have variables a and b as you have them, that is I would only have 1 variable, a, maintained by the loop and I would create b from a as required. 1 less thing to keep track of.

And finally even if you fix the logic errors this sorting algorithm will not work take this data example

9 Some text
10 More text
7 Further text

Your algorithm makes a single pass checking entry N against N+1 so after sorting the order would be

9 Some text
7 Further text
10 More text

which is still wrong.

You need to implement a proper sorting algorithm and rather than trying to make one up yourself I suggest looking one up http://en.wikipedia.org/wiki/Sorting_algorithms.

Another alternitive is to create the list sorted (I often do this) that is don't just create the linked list any old way but when you add an entry add it in the correct place to preserve your sorting (and that is a way of sorting too take entries off the current list and insert them into a new list in sorted order).