Thread: Bubble Sorting a Linked List

Originally Posted by rcgldr

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.

Originally Posted by iMalc

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?

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);
}

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.