Thread: Bubble sort on linked list not working.

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    Bubble sort on linked list not working.

    I know its sad, but I am having trouble getting a bubble sort to work. Its meant to sort text by iterating through the pointers in the list. Somethings wrong tho and it only seems to half-sort it. Heres the function:
    Code:
    void SortList(list *head)
    {
        list *here;
        list *there;
        char temp[SIZE];
        
        while(head->next != NULL)
        {    
            here=head;  
            while(1)
            {
                there=here->next;
                if(there == NULL) break; 
                  
                if(strcmp(here->data, there->data) >0)
                {
                    strcpy(temp, here->data);
                    strcpy(here->data, there->data);
                    strcpy(there->data, temp);
                }
                here=there;    
            }
            head=head->next;
        }     
    }
    And heres a full/compilable version:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define SIZE 100
    
    struct list
    {
        char data[SIZE];
        struct list *next;
    }; 
    typedef struct list list;
    
    list *NewNode(list **head);
    void PrintList(list *p);
    int CountList(list *p);
    void SortList(list *here);
    
    int main()
    {        
        char temp[SIZE];
        list *head=NULL;   
    
        while(1)
        {
            fgets(temp, SIZE, stdin);
            if(temp[0]=='\n')break; 
            temp[strlen(temp)-1]='\0';
            head=NewNode(&head);
            strcpy(head->data, temp);   
        }
        SortList(head);
        //BSort(head);
        PrintList(head);
        printf("List Entries: %i", CountList(head));
        getchar();
        
    }    
    
    list *NewNode(list **head)
    {
        list *newnode;
        //Allocate space for new item
        if(!(newnode = malloc(sizeof(*newnode))))
            return NULL;
        
        newnode->next=*head; //Next pointer is the existing head
        *head = newnode;     //Make the new node the head
        newnode->data[0]='\0';
        return newnode;
    }
    
    void PrintList(list *p)
    {
        while(p != NULL)
        {
            printf("Data: %s\t-\tAt Memory Address: %i\n", p->data, p);
            p=p->next;
        }     
    }
    
    int CountList(list *p)
    {
       int count=0;
       while(p != NULL)
       {
           count++;
           p=p->next;
       }
       return count;         
    }
    
    void SortList(list *head)
    {
        list *here;
        list *there;
        char temp[SIZE];
        
        while(head->next != NULL)
        {    
            here=head;  
            while(1)
            {
                there=here->next;
                if(there == NULL) break; 
                  
                if(strcmp(here->data, there->data) >0)
                {
                    strcpy(temp, here->data);
                    strcpy(here->data, there->data);
                    strcpy(there->data, temp);
                }
                here=there;    
            }
            head=head->next;
        }     
    }

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Just out of curiosity, why are you trying to bubble sort a linked list? The algorithm is completely unsuited to the data structure. The ideal solution is not to fix the bubble sort, but to switch to something more appropriate, like insertion sort, selection sort, or merge sort.
    My best code is written with the delete key.

  3. #3
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Why do you need a buble sort for the list? List is already suitable for insertion sort...

    PS. too slow
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Oh, yeah I guess I could do that. An insertion sort would be much faster for something like this. I'll have a go at it, but in the meantime if anyone can see whats wrong let us know

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >but in the meantime if anyone can see whats wrong let us know
    What's wrong is that you're modifying head, but still using it to control where the inner loop starts:
    Code:
    void SortList(list *head)
    {
        list *it = head;
        list *here;
        list *there;
        char temp[SIZE];
        
        while(it->next != NULL)
        {    
            here=head;  
            while(1)
            {
                there=here->next;
                if(there == NULL) break; 
                  
                if(strcmp(here->data, there->data) >0)
                {
                    strcpy(temp, here->data);
                    strcpy(here->data, there->data);
                    strcpy(there->data, temp);
                }
                here=there;    
            }
            it=it->next;
        }     
    }
    My best code is written with the delete key.

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    So thats what it was. I knew it had to be something stupidly simple like that. Thanks for finding it anyway. I'll still recode it so the items are inserted in order when they are made tho, as thats better. Cheers.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Although you're sorting a linked-list data structure, you are in fact not using a linked-list sorting algorithm! A linked-list sorting algorithm modifies the pointers in each node, not the item data.
    What you've implemented varies in execution time according to the size of the item, whereas it should take the same amount of time regardless of the item's data type. That's kinda much of advantage to using a list to begin with - cheap reordering.

    The actual Bubble Sort linked-list algorithm is not as trivial as you might think either.
    The shortest, and easiest to learn linked-list sorting algorithm, is Insertion Sort. I suggest learning that.
    When you feel you need something faster, learn Merge Sort.
    When that isn't fast enough, learn Bucket Sort.

    You'll find them all (and more) on my home page.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah originally I tried coding it so the sort would swap the pointers, but I screwed up and ended up with items pointing to themselves so I started from scratch swapping the data instead. Swapping the data should be quite a lot slower as theres more to copy tho. I started off coding something in my NewNode function to insert the data in sorted order but made a mess of that too. I guess maybe I'd be best off copying off some examples for now, I'll check out the stuff on your site. Cheers.

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >you are in fact not using a linked-list sorting algorithm!
    Alright then, what kind of sorting algorithm is it? Bubble sort is an exchange sort whether you exchange the data or the nodes. There's no distinction between a linked list algorithm and a non-linked list algorithm just because you work with the data rather than perform pointer surgery.

    >A linked-list sorting algorithm modifies the pointers in each node, not the item data.
    That's merely another way to sort a linked list. There are advantages and disadvantages of both methods.
    My best code is written with the delete key.

  10. #10
    Registered User
    Join Date
    Jun 2007
    Posts
    63
    Yes i cant agree more... When you want to sort a linked list you must exchange the whole nodes, this mens removing the node from one place and excanging with another node. In a single connect linked list i suppose that the trick is by writing a function that exchange two nodes, watch only for head and tail.
    Firstly you may implement a way to find the previous node. A function that does that is the following:
    Code:
    Node *GetPreviousNode(Node *p, List *l)                             
    {
         if(l && p)
         {
              Node *previous = NULL;
              for(previous = l->head; previous->next != p; previous = previous->next);
              return previous != NULL ? previous : NULL;
         }
         else
         return NULL;
    }
    This works in a List with node Node implementation. Return value is the whole node meaning that whatever holds inside can be used without any use or change. Now that you have the previous node, you can place the new node after him.
    eg. if Node *r = GetPreviousNode(q, l) then r->next can hold a new malloced node that has the value of the one to get exchanged. Remember to free the nodes in each situation.
    eg. The node to get freed that has previous node the node r from above, before we free him, supposing firstly we have created a new node similar to the exchanging node should firstly be used before free method because the
    newnode->next = (theNodeToGetFreed->next);
    free(theNodeToGetFreed);
    r->next = newnode;

    I want to think it by yourself, if you encounter any problems i can help you!!
    Last edited by Bokarinho; 07-03-2007 at 01:15 PM. Reason: forgot the free method... :)

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Prelude View Post
    >you are in fact not using a linked-list sorting algorithm!
    Alright then, what kind of sorting algorithm is it? Bubble sort is an exchange sort whether you exchange the data or the nodes. There's no distinction between a linked list algorithm and a non-linked list algorithm just because you work with the data rather than perform pointer surgery.

    >A linked-list sorting algorithm modifies the pointers in each node, not the item data.
    That's merely another way to sort a linked list. There are advantages and disadvantages of both methods.
    Okay so you got me. Yes it's still bubble sort, and in this case no there's no real difference between the array version and the list version.
    However a linked-list algorithm should always be implemented by pointer swapping IMHO, and if you don't do pointer swapping then it probably should be using an array data structure anyway. Otherwise you get abominations like what Bokarinho just posted that lead to O(n^3) or worse algorithms.

    There are very clear differences between algorithms such as insertion sort on a list vs an array. For example in the array version you can use a binary search to locate the place to put the item, whereas for a singly-linked-list you cannot. You also have to move items over to put each item in its place for the array version, whereas for the singly-linked-list version you do not. Insertion must be performed by scanning from the head end for a singly-linked-list to find the insertion point, whereas the array version can do either direction, but is usually better to do it coming back towards the start.
    So in the case of insertion sort at least there is a VERY distinct difference between the array algorithm and the singly-linked-list algorithm. That's what I mean, and where I am coming from.
    Last edited by iMalc; 07-03-2007 at 01:35 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >However a linked-list algorithm should always be implemented by pointer swapping IMHO
    You're certainly welcome to that opinion. And I don't entirely disagree either. But it never hurts to keep an open mind. For example, if you can swap data more efficiently than fiddling with pointers, and it's not designed to be generic, you can improve the performance of the sort quite a bit.

    >and if you don't do pointer swapping then it probably should be using an array data structure anyway.
    That means either using an array for the storage medium or using an array as a middle-man. The former doesn't always make sense and the latter is a fantastic way to drive up your performance and storage penalties.

    >Otherwise you get abominations like what Bokarinho just posted that lead to O(n^3) or worse algorithms.
    That's simply a case of not knowing what you're doing. An imbecile can write horrendous sorting algorithms using arrays too.

    >There are very clear differences between algorithms such as insertion sort on a list vs an array.
    Indeed, I haven't ever said otherwise.

    >That's what I mean, and where I am coming from.
    Of course. Random access gives you more options. Please don't take it as me saying that sorting on linked lists and arrays are the same. I'm just saying that pointer surgery isn't the only choice, or always the best choice.

    [edit]
    I like your website.
    [/edit]
    My best code is written with the delete key.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    >However a linked-list algorithm should always be implemented by pointer swapping IMHO
    You're certainly welcome to that opinion. And I don't entirely disagree either. But it never hurts to keep an open mind. For example, if you can swap data more efficiently than fiddling with pointers, and it's not designed to be generic, you can improve the performance of the sort quite a bit.
    Yeah I guess it can be faster in some cases.

    >and if you don't do pointer swapping then it probably should be using an array data structure anyway.
    That means either using an array for the storage medium or using an array as a middle-man. The former doesn't always make sense and the latter is a fantastic way to drive up your performance and storage penalties.
    I was thinking along the lines of it being better to use an array/vector over a list when you don't ever need to do things such as inserting or removing from places other than the end at all. Sorting via swapping the data would be another thing one can of course do which doesn't involve inserting or removing from places other than the end. Then with no need for inserting or removing anywhere but the end at all, it allows switching to an array (or rather a vector as I was actually thinking of) which becomes pretty logical as you no longer need the pointer overhead.
    It certainly wouldn't make sense to switch to an array if you ever did need to insert in the middle for exmaple.

    >Otherwise you get abominations like what Bokarinho just posted that lead to O(n^3) or worse algorithms.
    That's simply a case of not knowing what you're doing. An imbecile can write horrendous sorting algorithms using arrays too.
    Indeed, in fact I came across a worse than O(n^3) version of 'quicksort' on a list quite recently which is partly what prompted me to post some of what I did here. Quite a few people really don't get that it isn't good to treat a list as though it has random access.

    >There are very clear differences between algorithms such as insertion sort on a list vs an array.
    Indeed, I haven't ever said otherwise.
    I thought I must have misinterpreted you. Hope I didn't seem condescending. I know you are very much familiar with this stuff.

    >That's what I mean, and where I am coming from.
    Of course. Random access gives you more options. Please don't take it as me saying that sorting on linked lists and arrays are the same. I'm just saying that pointer surgery isn't the only choice, or always the best choice.
    Ok, point taken.

    [edit]
    I like your website.
    [/edit]
    Aw thanks! I feel like it is horribly unfinished at the moment. I tend to be too lazy to go into much detail about any one algorithm. I need to motivate myself some more. At least I got started finally.

    The changes you made to your site a little while ago look very nice! I don't think my html coding is up to that kind of thing yet.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  3. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM