Thread: Bubble Sorting a Linked List

  1. #1
    Registered User
    Join Date
    Sep 2014
    Posts
    74

    Red face Bubble Sorting a Linked List

    Hello guys,
    I wrote a code to bubble sort the elements of a linked list and its below. I couldn't understand how to apply bubble sort to a list so I copied the list's nodes into an array and applied bubble sort on that array (traditional method).
    I was curious whether this code is 'EFFICIENT', like a good programming practice?
    And how to apply bubble sort directly to linked list?

    Here's the code:
    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 array[9];
    // --- LIST ---
    struct numbers
    {
       int num;
       struct numbers *next;
    };
    
    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: \n");
    
        first_node=(struct numbers *)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");
    
             }
         }
    
         display();
         printf("\nTOTAL NUMBER OF NODES: %d",x);
         putchar('\n');
    
    
         // --- LIST TO ARRAY ---
    
         int i,array[x];
    
         array_node=first_node;
         for(i=0;i<x;i++)
         {
             array[i]= (array_node->num);
             array_node=array_node->next;
         }
    
         // --- BUBBLE SORT ---
         printf("Bubble sorted: \n");
         int outer,inner,tmp;
         for(outer=0;outer<x-1;outer++)
         {
             for(inner=outer+1;inner<x;inner++)
             {
                 if(array[outer]>array[inner])
                 {
                     tmp=array[outer];
                     array[outer]=array[inner];
                     array[inner]=tmp;
                 }
             }
         }
    
         for(i=0;i<x;i++)
         {
             printf("%d\t",array[i]);
         }
    
    
    
         return(0);
    }
    
    //--- FUNCTIONS ---
    
    void create_node()
    {
        new_node=(struct numbers*)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 list: \n");
    
        temp=first_node;
        while(temp!= NULL)
        {
            printf("%d\t",temp->num);
            temp=temp->next;
        }
    }
    Thanks.

    EDIT: Yes I know that I shouldn't typecast malloc()
    Last edited by Sankait Laroiya; 10-10-2014 at 10:40 AM.

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,773
    Global variables are consider bad practice.

    NOTE: EFFICIENT and bubble sort are NOT normally used together.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    4,498
    First do you realize that you're using a VLA in the following snippet:

    Code:
    int x=1;
    ...
        while(choice == 'y' || choice== 'Y')
         {
             x++;
     ...
     
     
         // --- LIST TO ARRAY ---
     
         int i,array[x];  // Note the non compile time constant array size.
    To answer your question, IMO, if you want the information in your list sorted you'd probably be better off inserting them in this sorted order.

    Jim

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    3,773
    I would have used the idea of insertion sort and created a second link list.
    NOTE: Sorting the first link list in place would likely be considered more EFFICIENT by some measures; but, it is harder to do.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,651
    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.
    Last edited by rcgldr; 10-10-2014 at 12:27 PM.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    Quote Originally Posted by Sankait Laroiya View Post
    EDIT: Yes I know that I shouldn't typecast malloc()
    Then why the heck are you still doing it? Clearly we've told you that before. How do you think we feel about volunteering our little bit of free time and energy giving advice and help to people that don't listen to us?
    Quote Originally Posted by Sankait Laroiya View Post
    Hello guys,
    I wrote a code to bubble sort the elements of a linked list and its below. I couldn't understand how to apply bubble sort to a list so I copied the list's nodes into an array and applied bubble sort on that array (traditional method).
    I was curious whether this code is 'EFFICIENT', like a good programming practice?
    And how to apply bubble sort directly to linked list?
    Bubble sort is not efficient no matter what the data type (the "smart" version that bails out if no swaps were made is only efficient when the data is already sorted). Sure it's not horrible, but it's not very good. Insertion/selection sorts would do a bit better for linked lists, but still not great. Merge sort (IIRC bottom-up in particular) is pretty good.

    Something I will mention that you should consider general advice that applies to all your questions, not just this one:
    You are almost certainly not the first person to wonder about this or ask this question. There's likely a fair amount of research and information about this out there; you should try doing some research first. A Google search for "sorting a linked list" would be a great place to start.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,651
    Quote Originally Posted by anduril462 View Post
    Merge sort (IIRC bottom-up in particular) is pretty good.
    Using an array of 32 (or less) list pointers where the number of nodes in arrray[i] is 2^i, and merging nodes into the array, then merging the array is probably the fastest method. In addition to the array, you need two working list pointers, one for one of the merge input parameters, and one for merge output. This is how it's implemented in std::list::sort in Microsoft STL.

  8. #8
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Some modifications as suggested:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // --- FUNCTION PROTOTYPES ---
    void create_node();
    void remove_newline();
    char append();
    void display();
    void bubble_sort(int *array);
    
    // --- GLOBAL VARIABLES ---
    int x=1;
    
    // --- LIST ---
    struct numbers
    {
       int num;
       struct numbers *next;
    };
    
    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);
    
         // --- LIST TO ARRAY ---
         int i,*array[x];
    
         array_node=first_node;
         for(i=0;i<x;i++)
         {
             array[i]= (int *)(array_node->num);
             array_node=array_node->next;
         }
    
         bubble_sort((int *)array);
    
        // --- DISPLAY SORTED ARRAY ---
         for(i=0;i<x;i++)
         {
             printf("%d\t",(int)array[i]);
         }
    
    
    
         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 list: \n");
    
        temp=first_node;
        while(temp!= NULL)
        {
            printf("%d\t",temp->num);
            temp=temp->next;
        }
    }
    
    void bubble_sort(int *array)                   // --- BUBBLE SORT ---
    {
         printf("Bubble sorted: \n");
         int outer,inner,tmp;
         for(outer=0;outer<x-1;outer++)
         {
             for(inner=outer+1;inner<x;inner++)
             {
                 if(array[outer]>array[inner])
                 {
                     tmp=array[outer];
                     array[outer]=array[inner];
                     array[inner]=tmp;
                 }
             }
         }
    }
    Removed unwanted global variables.
    Used array of pointers to convert list data into array.
    Moved bubble sort into seperate function.
    Removed typecasting for malloc().

    Quote Originally Posted by stahta01 View Post
    Global variables are consider bad practice.

    NOTE: EFFICIENT and bubble sort are NOT normally used together.

    Tim S.
    I had to declare structure global because it went into more than one different function. And I used x to count those nodes so I declared it global. I removed the other one and tried to minimize the use of global variables.

    Quote Originally Posted by jimblumberg View Post
    First do you realize that you're using a VLA in the following snippet
    Yes, I realize. I did it so because I wanted to make sure that the size of array needed to sort the list is equal to the number of nodes.

  9. #9
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by anduril462 View Post
    Then why the heck are you still doing it? Clearly we've told you that before. How do you think we feel about volunteering our little bit of free time and energy giving advice and help to people that don't listen to us?
    Please don't go all angry over me. I wrote the code some time ago. Then I didn't know that malloc() doesn't need to be typecasted always. If you want to share your knowledge, you are welcome. I appreciate what people do by helping others in this forum and If I wanted to ignore you then I wouldn't even have mentioned that line. Thanks and no offense intended.

    Quote Originally Posted by anduril462 View Post
    Bubble sort is not efficient no matter what the data type (the "smart" version that bails out if no swaps were made is only efficient when the data is already sorted). Sure it's not horrible, but it's not very good. Insertion/selection sorts would do a bit better for linked lists, but still not great. Merge sort (IIRC bottom-up in particular) is pretty good.
    I haven't learnt any other sorts yet. So, I used this one.

    Quote Originally Posted by anduril462 View Post
    Something I will mention that you should consider general advice that applies to all your questions, not just this one:
    You are almost certainly not the first person to wonder about this or ask this question. There's likely a fair amount of research and information about this out there; you should try doing some research first. A Google search for "sorting a linked list" would be a great place to start.
    You don't realize how much I try to solve the problem before coming here. You think I come here ranting about my problems without trying to solve them myself in first place,well, you are wrong. I am an infant in programming (study level: 12th grade) and if you don't humbly want to help, then what are you doing here. I appreciate the time you spent to help me, but you are not supposed to boss over the people you help. So, shut it on that one.
    Again, I don't want to offend you or disrespect you. Thanks.

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    3,773
    I think learning to bubble-sort a link list is a waste of time.
    You should instead as I suggested before re-write the link list to support insertion sort.

    FYI: You are using C casts a lot; this is often a sign of design or implementation mistakes.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  11. #11
    Registered User
    Join Date
    May 2010
    Posts
    4,498
    Yes, I realize. I did it so because I wanted to make sure that the size of array needed to sort the list is equal to the number of nodes.
    Do you also realize that VLA are not supported with all/most compilers? And that VLA are only truly supported by the C99 C standard, they are not allowed in previous standards and are optional in the later C standards?

    I really recommend you think about using "normal" dynamic memory (malloc/free) if you really desire this functionality.


    Jim

  12. #12
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by stahta01 View Post
    I think learning to bubble-sort a link list is a waste of time.
    You should instead as I suggested before re-write the link list to support insertion sort.

    FYI: You are using C casts a lot; this is often a sign of design or implementation mistakes.

    Tim S.
    When I learn other sorts I will leave bubble sort.
    At two instances I got warnings from my IDE. It said that I was trying to assign a an in from a pointer, so I typecasted the pointer to int so the warnings disappeared. I usually donot typecast in my code.

  13. #13
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by jimblumberg View Post
    Do you also realize that VLA are not supported with all/most compilers? And that VLA are only truly supported by the C99 C standard, they are not allowed in previous standards and are optional in the later C standards?

    I really recommend you think about using "normal" dynamic memory (malloc/free) if you really desire this functionality.


    Jim
    Then in my code the array under LIST TO ARRAY comment will be allocated memory like so? Right? :
    Code:
    int *array = malloc(sizeof(int) *x) ;
    and this pointer will be incremented with array++?
    And could you please elaborate the problem behind assigning an array its size during runtime?
    Thanks.

  14. #14
    Registered User
    Join Date
    May 2010
    Posts
    4,498
    At two instances I got warnings from my IDE. It said that I was trying to assign a an in from a pointer, so I typecasted the pointer to int so the warnings disappeared. I usually donot typecast in my code.
    Casting to avoid compiler warnings is usually not a good idea. And the following is IMO a very poor use of the cast.

    Code:
         // --- LIST TO ARRAY ---
         int i,*array[x];
    
         array_node=first_node;
         for(i=0;i<x;i++)
         {
             array[i]= (int *)(array_node->num);
             array_node=array_node->next;
         }
    
         bubble_sort(array);
    Why is array a pointer to an array of int in the first place? And since the array[x] is a VLA that makes things even worse.

    Jim

  15. #15
    Registered User
    Join Date
    Sep 2014
    Posts
    74
    Quote Originally Posted by jimblumberg View Post
    Casting to avoid compiler warnings is usually not a good idea. And the following is IMO a very poor use of the cast.

    Code:
         // --- LIST TO ARRAY ---
         int i,*array[x];
    
         array_node=first_node;
         for(i=0;i<x;i++)
         {
             array[i]= (int *)(array_node->num);
             array_node=array_node->next;
         }
    
         bubble_sort(array);
    Why is array a pointer to an array of int in the first place? And since the array[x] is a VLA that makes things even worse.

    Jim
    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?

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