Thread: Bubble Sorting a Linked List

  1. #16
    Registered User
    Join Date
    May 2010
    Posts
    4,539
    array_node->num is an int and to avoid warning I typecasted it to an int pointer and assigned it to int array.
    How would you suggest to modify it?
    Actually fix the code instead of just shutting up the compiler. Those warnings are telling you something, you should listen.

    What is the purpose of the pointer in *array[x]?

    Jim

  2. #17
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    The code you have sorts an array of integers, not a list, have you changed your mind about what the goal of this project is? Also you could allocate the space for the array (don't forget to free it when done):

    Code:
    // --- LIST TO ARRAY --- 
        int i, *array;
        array = malloc(x * sizeof(int));

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by rcgldr View Post
    Note that you could have sorted the nodes by creating an array of pointers to those nodes in the linked list and sorting via the pointers. Implementing a bubble sort with a single linked list could be done by repeatedly moving the "largest" node to the end of the list, then removing that node from the list and inserting it at the beginning of a the "currently sorted" list, using a second list pointer. When completed, the original list pointer would be NULL and the second list pointer would point to the first node of the sorted list.
    In other words - Selection Sort.
    Which of course you could also easily do without making an array first, and it's still easier than Bubble Sorting a linked-list.

    OP:
    You are not actually Bubble Sorting a list, you are Bubble Sorting an array. To do it on an array is very easy, but doing it on a linked list is very hard. Had you been actually Bubble Sorting a linked-list you would probably not have succeeded.
    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"

  4. #19
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by iMalc View Post
    In other words - Selection Sort.
    Which of course you could also easily do without making an array first, and it's still easier than Bubble Sorting a linked-list.

    OP:
    You are not actually Bubble Sorting a list, you are Bubble Sorting an array. To do it on an array is very easy, but doing it on a linked list is very hard. Had you been actually Bubble Sorting a linked-list you would probably not have succeeded.
    Well, I tried and came up with this:
    Code:
    struct numbers *a,*b;                         
         int swapper;
    
    
         a=first_node;
         b=first_node->next;
    
         while(b != NULL)
         {
             if((a->num) > (b->num))
             {
                 swapper=a->num;
                 a->num=b->num;
                 b->num=swapper;
             }
             if(b == NULL)
             {
                 break;
             }
             a=a->next;
             b=b->next;
         }
    But it doesn't work. Any suggestions?
    Last edited by Sankait Laroiya; 10-12-2014 at 04:14 AM.

  5. #20
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by rcgldr View Post
    The code you have sorts an array of integers, not a list, have you changed your mind about what the goal of this project is? Also you could allocate the space for the array (don't forget to free it when done):

    Code:
    // --- LIST TO ARRAY --- 
        int i, *array;
        array = malloc(x * sizeof(int));
    No I didn't change my mind. I wanted to sort the contents of the list. So, I thought I could copy it into an array and then sort the array with bubble sort, actually the list remains the same. I couldn't figure out the method to sort the linked list directly with bubble sort. See the post above this one.

  6. #21
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    GOT IT WORKING!
    I tried to go through the loop by hand and figured out this code which now works. But I don't know if its efficient, but something is better than nothing. Check it out:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    // --- FUNCTION PROTOTYPES ---
    void create_node();
    void remove_newline();
    char append();
    void display();
    
    
    // --- GLOBAL VARIABLES ---
    int x = 1;
    int i;
    // --- LIST ---
    struct numbers
    {
       int num;
       struct numbers *next;
    };
    void bubble_sort(struct numbers *a);
    struct numbers *first_node;
    struct numbers *current_node;
    struct numbers *new_node;
    struct numbers *temp;
    struct numbers *array_node;
    
    
    int main()
    {
    
        printf("Hello!, input the numbers below: \n\n");
    
        first_node=malloc(sizeof(struct numbers));
        if(first_node== NULL)
        {
            puts("Memory allocation failed!");
            return(0);
        }
        current_node=first_node;
        printf("Input the #%d value: ", x);
        scanf("%d", &current_node->num);
    
        remove_newline();
        char choice=append();
    
        while(choice == 'y' || choice== 'Y')
         {
             x++;
             create_node();
             remove_newline();
             choice = append();
         }
        if( choice == 'n' || choice == 'N')
             {
                 current_node->next=NULL;
                 new_node->next=NULL;
                 printf("Okay, then. Bye\n\n");
    
             }
        else
        {
            printf("Invalid Input!");
            return(0);
        }
    
         display();
         printf("\n\nTOTAL NUMBER OF NODES: %d\n\n",x);
    
         struct numbers *a;
         a=first_node;
    
         bubble_sort(a);
    
    
         a=first_node;
         for(i=0;i<x;i++)
         {
             printf("%d\t",a->num);
             a=a->next;
         }
    
         return(0);
    }
    
    //--- FUNCTIONS ---
    
    void create_node()
    {
        new_node=malloc(sizeof(struct numbers));
        current_node->next=new_node;
        if(new_node==NULL)
        {
            puts("Memory allocation failed");
        }
            current_node=new_node;
            printf("Input #%d number: \n",x);
            scanf("%d",&current_node->num);
    }
    
    void remove_newline()
    {
        while(getchar() != '\n')
            ;
    }
    
    char append()
    {
        printf("\nDo you want to add more numbers in the list? Y/N: ");
        char choice;
        scanf("%c", &choice);
        putchar('\n');
        return(choice);
    }
    
    void display()
    {
        printf("Here is the unsorted list: \n");
    
        temp=first_node;
        while(temp!= NULL)
        {
            printf("%d\t",temp->num);
            temp=temp->next;
        }
    }
    
    void bubble_sort(struct numbers *a)
    {
        struct numbers *b;
        int temp;
    
        b=a->next;
        for(i=0;i<x;i++)
        {
           while( b != NULL )
               {
                  if(a->num > (b->num))
                     {
                        temp=a->num;          // SWAPPING NUMBERS
                        a->num=(b->num);
                        (b->num)=temp;
    
                     }
                        a=a->next;     // INCREMENT POSITIONS OF a & b
                        b=a->next;
               }
                        a=first_node;            // RESET THE POSITION OF a & b
                        b=a->next;
        }
    }
    Thank you guys for mulling over the problem for me

  7. #22
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by Sankait Laroiya View Post
    figured out this code which now works.
    It's still just swapping the numbers in the nodes as opposed to swapping the nodes (which can be done by changing the next pointers in the nodes), and it's using an integer i for the outer loop when it would be better to use another pointer to a node. As mentioned before, you could use two lists, the original list and a second list that starts off as an empty list. You then move the node with the largest number to the end of the first list, then remove it from the end of the first list and insert it into the beginning of the second list, until the first list is empty and the second list contains all the nodes in sorted order.

  8. #23
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by rcgldr View Post
    It's still just swapping the numbers in the nodes as opposed to swapping the nodes (which can be done by changing the next pointers in the nodes), and it's using an integer i for the outer loop when it would be better to use another pointer to a node. As mentioned before, you could use two lists, the original list and a second list that starts off as an empty list. You then move the node with the largest number to the end of the first list, then remove it from the end of the first list and insert it into the beginning of the second list, until the first list is empty and the second list contains all the nodes in sorted order.
    Well, I did what I wanted to do actually, the position of the numbers in the list matter so the adresses exchange the numbers only. So, instead of moving about the nodes, I just make them interchange the numbers. But I will try to implement what you suggest. Thanks bro.

  9. #24
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Since a bubble sort for a linked list is not efficient, I made an example function (I had bits and pieces of code I could use for this, so there's no need for you to spend time trying to create this from scratch). I tested using 65,536 nodes with 64 bit unsigned integers for data, which took about 17.5 seconds on my system (Intel 2600K, 3.4ghz, 32 bit mode). A merge sort that uses a small (32) array of pointers to list took less than 1/32 second. The merge / array sort can sort 4,194,304 nodes in 1.2 seconds, while the bubble sort would take around 72,000 seconds, just under 20 hours, so it's not an efficient way to implement a list sort.

    Code:
    typedef unsigned long long UI64;
    
    typedef struct NODE_{
    struct NODE_ * next;
    UI64 data;
    }NODE;
    
    NODE * SortList(NODE * pList)
    {
    NODE * pNew = NULL;                             /* sorted list */
    NODE **ppCur;                                   /* head or previous node */
    NODE *pCur;                                     /* current node */
    NODE *pNxt;                                     /* next node */
    NODE *pTmp;
    
        while(pList != NULL){                       /* while list not empty */
            ppCur = &pList;                         /*   move largest to end */
            while(NULL != (pNxt = (pCur = *ppCur)->next)){
                if(pCur->data > pNxt->data){
                    pTmp = pNxt->next;
                    pNxt->next = pCur;
                    pCur->next = pTmp;
                    *ppCur = pNxt;
                }
                ppCur = &((*ppCur)->next);
            }
            *ppCur = NULL;                          /* move node to new */
            pCur->next = pNew;
            pNew = pCur;
        }    
        return(pNew);
    }
    Last edited by rcgldr; 10-14-2014 at 12:55 AM.

  10. #25
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by rcgldr View Post
    Since a bubble sort for a linked list is not efficient, I made an example function (I had bits and pieces of code I could use for this, so there's no need for you to spend time trying to create this from scratch). I tested using 65,536 nodes with 64 bit unsigned integers for data, which took about 17.5 seconds on my system (Intel 2600K, 3.4ghz, 32 bit mode). A merge sort that uses a small (32) array of pointers to list took less than 1/32 second. The merge / array sort can sort 4,194,304 nodes in 1.2 seconds, while the bubble sort would take around 72,000 seconds, just under 20 hours, so it's not an efficient way to implement a list sort.

    Code:
    typedef unsigned long long UI64;
    
    typedef struct NODE_{
    struct NODE_ * next;
    UI64 data;
    }NODE;
    
    NODE * SortList(NODE * pList)
    {
    NODE * pNew = NULL;                             /* sorted list */
    NODE **ppCur;                                   /* head or previous node */
    NODE *pCur;                                     /* current node */
    NODE *pNxt;                                     /* next node */
    NODE *pTmp;
    
        while(pList != NULL){                       /* while list not empty */
            ppCur = &pList;                         /*   move largest to end */
            while(NULL != (pNxt = (pCur = *ppCur)->next)){
                if(pCur->data > pNxt->data){
                    pTmp = pNxt->next;
                    pNxt->next = pCur;
                    pCur->next = pTmp;
                    *ppCur = pNxt;
                }
                ppCur = &((*ppCur)->next);
            }
            *ppCur = NULL;                          /* move node to new */
            pCur->next = pNew;
            pNew = pCur;
        }    
        return(pNew);
    }
    I don't know merge sort yet, only bubble sort. So, I used it. But thanks for this code

  11. #26
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    Regarding your post #9, I wasn't trying to be rude or arrogant, though I feel no obligation to be particularly humble when I help. If I see a problem, or think I have something worth saying, I say so, frankly; not rude, just direct. I will also point out bad decisions like not fixing code you know is wrong. It would take you less than a minute to remove the casts from the malloc calls, but you didn't do it. I suggested other sorting algorithms for you to look into as they are more efficient (which you asked about) and easier to implement with linked lists too. While it may be true that you did research already, we are not mind readers. You didn't say "I already read x, y and z about this topic", so how were we to know? I suggested you search and read because there's tons of excellent info already out there -- I did this because I thought, if you did any research (as you claim), you would have realized that bubble sort is NOT the way to go with linked lists. I also genuinely thought you would benefit from some research and reading. There's way more good info already out there than we could possibly fit into this thread.

    You asked about efficiency. This has been stated many times in this thread, and this information is all over Wikipedia and the internet, but here it is nonetheless:
    Your code is about as efficient (in run-time) as you can get using bubble sort. Unfortunately, bubble sort is by it's very nature not efficient; it is O(n**2) under average- and worst-cases. We've mentioned insertion and selection sort, which are both O(n**2) as well, but easier to implement directly on a linked list (without a temp array). However merge sort is O(n log n), which is a significant improvement over O(n**2) algorithms. That's your best bet for sorting linked lists.

    You keep saying "I don't know merge sort yet". We're saying "learn it". Go read some articles on it, try some small examples with arrays first.

    You asked about "best programming practice". Your code makes a decent attempt to implement some good practices but falls short in many areas. Some of this you know better, some of it will come with experience.

    As has been pointed out, global variables are a bad practice, and should only be used if absolutely necessary -- they aren't necessary in your program at all. You should declare all the variables in appropriate functions and pass them into any other functions that need them. If you learn to do things the right way early on, you life as a programmer will be much easier. We told you it's bad. You claimed you attempted to remove globals, but there are 7 in your first post, and 7 in your latest post with code. You should have 0.

    Functions have two broad purposes: to break code up into logical sections and make it easier to read, and to make blocks of reusable code so you don't have to type the same thing over and over again. Another fundamental concept regarding functions is that a function should do one thing and do it well.

    I will make some other suggestions though:

    • Your functions and function prototypes should use void as the parameter list if you don't want them to take any parameters. void means exactly zero. If you leave it blank, the compiler interprets that as "pass any number and type of parameters", making it impossible for the compiler to tell you if you are calling the function incorrectly.
    • It's more robust to read a whole line of input with fgets, and use a function to extract a numeric/integer value. I prefer strtol and strtod functions (more featureful and better error handling), but sscanf (the extra s is for scanning a string) will work also.
    • The above is nice for another reason. You can have a single input prompt that says something like "Enter a number for the list, or type 'done' to end input: ". That way the user doesn't have to type 'y' after every node.
    • do-while loops are usually a bit easier/better for user input. They always execute at least once so unlike a while loop, you don't need to replicate the "ask the user and get an answer" both before and inside the loop. See below
    • If you user makes a mistake and hits some other letter besides 'y' or 'n', you exit immediately. You should give them a chance to input a valid answer.
    • It's good to see you're making an attempt at organizing your code and breaking it down into functions, however you could use some improvement -- this comes largely with experience. Functions should do one thing and do it well -- a create_node function should not ask for input (though you can pass it an int parameter with the value for the new node). display should only display the list, not things like "Here is the unsorted list". That way you can reuse the function for displaying any list, at any point in your program; currently you have to repeat the display code in main after you sort.
    • Also, the names of some of your functions and variables are not great. append() sounds like it appends a node to the list (i.e. adds it to the end) when instead it checks if the user wants to enter more numbers. Something like user_has_more_input() is a more accurate and descriptive name. I've already mentioned create_node.
    • Your remove_newline function is good, but it does more than just remove a new line. Something like flush_input_line is better. Also, you should clear to newline or EOF. See below for an example
    • It's often a sign of good design, or at least good code organization and good function names, if your functions read like a summary of what they are doing. Your main function should be a summary of your whole program, other larger functions a summary of their respective sub-tasks. Smaller function can just contain the commands they need. Starting with planning on paper and pseudo code helps you produce organized code. Again, see below.


    getting input
    Code:
    do {
        print "Enter a number for the list, or 'done' to end"
        read line
        flush_input_buffer();  // see below
        if sscanf reads a number from input line
            append_to_list(list, number)
        else if line is 
            done = true;
        else
            print "Invalid input"
    } while (!done);
    clearing input
    Code:
    void flush_input_buffer(void)
    {
        int ch;  // getchar takes an int so it can return all char values and special values like EOF
    
    
        while ((ch = getchar()) != '\n' && ch != EOF)  // also check for EOF
            ;
    }
    main function that reads like a nice summary
    Code:
    int main(void)
    {
        get_list(...);
        print "The unsorted list is: "
        print_list(...);
        sort_list(...);
        print "The sorted list is: "
        print_list(...);
        return 0;
    }
    Each of those functions would then be fleshed out and, where appropriate, would itself be written as a summary, calling other, smaller functions.
    Last edited by anduril462; 10-14-2014 at 10:42 AM. Reason: small clarification

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubble sorting singly link list
    By Roaring_Tiger in forum C Programming
    Replies: 2
    Last Post: 09-08-2004, 05:44 AM
  2. bubble sort in a linked list
    By condorx in forum C++ Programming
    Replies: 1
    Last Post: 12-08-2002, 08:41 AM
  3. Linked list bubble sort
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 11-01-2001, 11:54 AM
  4. bubble sorting in linked list
    By anu in forum C Programming
    Replies: 4
    Last Post: 10-17-2001, 06:58 PM
  5. bubble sorting in linked list
    By anu in forum C Programming
    Replies: 0
    Last Post: 10-17-2001, 03:21 PM