Sorting (Doubly) Linked List using Bubble Sort in C

Let’s state the obvious first, Bubble Sort is the easiest among sorting algorithms to be implemented. It has O(1) space complexity as it only require one (temporary) additional variable for swapping. The best case time complexity is O(n) when the list is already sorted.

The problem with Bubble Sort is its worst time complexity. O(n^2) complexity makes its highly unlikely to be chosen as the algorithm to sort large lists.

Why O(n^2) though?

Bubble Sort checks whether an element is larger than its adjacent neighbor, if it is, they are swapped. This event goes on until the end of the list and the largest element will be place in its correct location. Then repeat this trend for the second time, then third, fourth, and so on.

So it takes (n-1) steps on the first pass, (n-2) on the second, (n-3) on the third, so on and so forth. High school algebra tells us this series equals n(n-1)/2. Hence the O(n^2) part.

---

My assignment this week was sorting a (doubly) linked list. Given the number of nodes only reaches 6 at max. So I thought, “Yeah, just the right number for Bubble Sort”. Plus, my teacher didn’t specify what algorithms to use.

First, the list

I have another post here about creating a singly linked list. Not much of a difference to doubly, only this time, the node have the address of the previous node.

 Code  | Course Name                 | Date | Room
 --------------------------------------------------------
 dat2x  data atructures                12     409
 comp3  introduction to programming    30     410
 comp4  algorithm and programming      15     408
 os12x  operating aystems              28     413
 algo2  algorithm design and analysis  4      409
 progx  advance oop                    2      422 

Above is an exam schedule. So the each node has the attributes: code, course name, date, and room. Now, let’s say I want all of them to be listed according to the dates. How can I accomplish that only given the starting node and the nodes struct only?

First and foremost, this is the struct

struct doublyNode {
     struct doublyNode *previous;
     char code[5];
     char name[50];
     short date;
     char room[5];
     struct doublyNode *next;
 }*newNode, *startNode; 

By now you may have noticed I’m using the camelCase. I picked it up when I was learning iOS development.

To sort those guys, we need two pointers and one additional variables as a flag.

struct doublyNode *pointer;
struct doublyNode *previousPointer = NULL; 
swapped = 0;

If you have taken OS classes before, you may know what a flag (or semaphore) is. Basically, it’s a signalling entity. In this case, the variable “swapped” is a binary semaphore: only takes two values: 1 if a swapping occurs and 0 (the default) if none occurs.

if(pointer->date pointer->next->date){
     swapInt(pointer, pointer->next);    //I’ll explain these
     swapString(pointer, pointer->next); //in another blog post
                   
     swapped = 1;
}

Above code is the core of Bubble Sort: “If an element is greater than its adjacent neighbor, swap them.”  We’ll cover the swapping algorithms later. For now, you only need to know the essence of Bubble Sort. Plus, if a swapping occurs, change the value of the flag to 1.

Now a problem occur. In the last pass, the value of pointer->next will be a NULL. So the if condition above will throw an error because we’re dereferencing a null value. What do we need to do?

if (pointer->next != NULL) { 
     ...
     //Put the previous codes here
     ... 
}

We need to contain the previous codes in an IF statement. If the “next” attribute of the pointer points to null, don’t execute (actually don’t bother to check for) the swapping algorithm.

After that we need to contain the codes again in a WHILE statement, so that the swapping algorithm will check for every two adjacent neighbor. Additionally, we need to add pointer- = pointer->next to point our pointer (sorry for the pun) to the next node.

while(pointer!=prevPointer) {
     ...
     //Put the previous codes here
     ... 
     ...        
     pointer = pointer->next;
}

Finally, we contain (what? again!?) the previous codes into a DO-WHILE loop to allow the swapping algorithm go for a second, third, fourth pass, and so on.

Why did I choose a do-while?

Because the default value for “swapped” is 0. If I chose a basic while loop, the code will never execute as the while loop’s condition is the value of “swapped”. Remember, the value 1 evaluates to true in C (and many other programming language).

So in the end, the final code will look like this:

do {
     swapped = 0;
     pointer = startNode;
         
     while(pointer!=prevPointer) {
         if (pointer->next != NULL) {
             if(pointer->date > pointer->next->date){
                 
                 //I’ll explain these two statements
                 //in another blog post
                 swapInt(pointer, pointer->next); 
                 swapString(pointer, pointer->next);
                 
                 swapped = 1;
             }
         }
         pointer = pointer->next;
     }
     prevPointer = pointer;
} while(swapped); 

Complete.