Home Discussions Write at Opengenus IQ
×

Search anything:

Bubble Sort on Linked List

Binary Tree book by OpenGenus

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have presented the approach to implement Bubble Sort on Singly Linked List and Doubly Linked List along with implementations in C and C++.

Table of contents:

  1. Introduction to Linked List
  2. Introduction to Bubble Sort
  3. Bubble Sort on Linked List

Prerequisite: Linked List, Bubble Sort

Introduction to Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.It consists of nodes where each node contains a data field and a reference(link) to the next node in the list. There are many types of linked list:

  1. Singly linked list
  2. Doubly linked list
  3. Circular linked list

Introduction to Bubble Sort

Let's throw some light on Bubble sort that what is bubble sorting technique and how it works.It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.You will clearly understand how it works after seeing this below mentioned example.

Example:
First Pass:
( 6 1 5 3 8 ) –> ( 1 6 5 3 8 ), Here, algorithm compares the first two elements, and swaps since 6 > 1.
( 1 6 5 3 8 ) –> ( 1 5 6 3 8 ), Swap since 6 > 5
( 1 5 6 3 8 ) –> ( 1 5 3 6 8 ), Swap since 6 > 3
( 1 5 3 6 8 ) –> ( 1 5 3 6 8 ), Now, since these elements are already in order (8 > 6), algorithm does not swap them.

Second Pass:
( 1 5 3 6 8 ) –> ( 1 5 3 6 8 )
( 1 5 3 6 8 ) –> ( 1 3 5 6 8 ), Swap since 5 > 3
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )

Bubble Sort on Linked List

Now let's talk about how this technique works in linked list. Given a linked list and we have to sort it using bubble sort method.Let's see what will be the steps involved or you can say passes in this technique to sort a given linked list.

Approach:First we have to form a linked list by inserting the values one by one and after insertion first we will point a head pointer towards the first node and keep on checking whether the current node data where the pointer is currently present is smaller,bigger or equal to the next node value. If the current node value is smaller or equal to next node value we will move our pointer further and point it towards the next node but if the current node value is bigger as compared to the next node value then we will swap the nodes with each other and make our pointer point towards the next node or that node which is swapped recently and keep on performing these passes until we will get the sorted list.

Input: 12->35->2->67
Now we have to sort this list we have inserted the node values and now we start traversing the given list.
First pass:
(12->35->2->67) => (12->35->2->67) as our pointer is pointing at 12(bolder part) and after comparing it with next node value we can see that 35>12 so we will not do anything just simply move our pointer point towards next node i.e, 35.
(12->35->2->67) => (12->2->35->67) now 35>2 so we will swap the adjacent nodes and move our pointer at third node which is again 35.
(12->2->35->67) => (12->2->35->67) as our pointer is pointing at 35(bolder part) and after comparing it with next node value we can see that 67>35 so we will not do anything just simply move our pointer point towards next node i.e, 67.
Now there is no node value next to the current node so we will move to the second pass.

Second pass:
(12->2->35->67) => (2->12->35->67) now our pointer is at 12 and as 12>2 so we will swap the adjacent nodes and move our pointer at second node which is again 12.
(2->12->35->67) => (2->12->35->67) as our pointer is pointing at 12 and after comparing it with next node value we can see that 35>12 so we will not do anything just simply move our pointer point towards next node i.e, 35.
(2->12->35->67) => (2->12->35->67) as our pointer is pointing at 35 and after comparing it with next node value we can see that 67>35 so we will not do anything just simply move our pointer point towards next node i.e, 67.
Now again no other node present next to the current node and we can see that our list becomes sorted but in this technique it will take an extra pass with no swaps so check whether the list is completely sorted or not.

Third pass:
(2->12->35->67) => (2->12->35->67) no swapping required
(2->12->35->67) => (2->12->35->67) no swapping required
(2->12->35->67) => (2->12->35->67) no swapping required
(2->12->35->67) => (2->12->35->67) no swapping required
As we clearly see that no swapping is required so we can say that our list has been sorted.

Now after having a clear understanding of how bubble sorting on linked list works we will write code for this in both C and in C++.

C implementation of Bubble Sort on Linked List:

// C program to implement Bubble Sort on singly linked list
#include<stdio.h>
#include<stdlib.h>

//structure of a node
struct Node
{
	int data; //value of a node
	struct Node *next; 
};

//Function to insert a node at the beginning of a linked list 
void insertAtTheBegin(struct Node **start_ref, int data);

//Function to bubble sort the given linked list
void bubbleSort(struct Node *start);

//Function to swap data of two nodes a and b
void swap(struct Node *a, struct Node *b);

//Function to print nodes in a given linked list
void printList(struct Node *start);

int main()
{
	int a[] = {11,32,56,2,8,9};
	int size, i;
	struct Node *head = NULL;

	for (i = 0; i< 6; i++)
		insertAtTheBegin(&head, a[i]); //function calling for inserting elements
        
	//print list before sorting
	printf("\n Linked list before sorting ");
	printList(head);

	//sort the linked list
	bubbleSort(head);

	//print list after sorting
	printf("\n Linked list after sorting ");
	printList(head);

	getchar();
	return 0;
}


//Function to insert a node at the beginning of a linked list
void insertAtTheBegin(struct Node **start_ref, int data)
{
	struct Node *ptr1 = (struct Node*)malloc(sizeof(struct Node));
	ptr1->data = data;
	ptr1->next = *start_ref;
	*start_ref = ptr1;
}

//Function to print nodes in a given linked list
void printList(struct Node *start)
{
	struct Node *temp = start;
	printf("\n");
	while (temp!=NULL)
	{
		printf("%d ", temp->data);
		temp = temp->next;
	}
}

//Bubble sort the given linked list
void bubbleSort(struct Node *head)
{
	int swapp, i;
	struct Node *ptr1;
	struct Node *lptr = NULL;

	/* Checking for empty list */
	if (head == NULL)
		return;

	do
	{
		swapp = 0;
		ptr1 = head;

		while (ptr1->next != lptr)
		{
			if (ptr1->data > ptr1->next->data)
			{
				swap(ptr1, ptr1->next);
				swapp = 1;
			}
			ptr1 = ptr1->next;
		}
		lptr = ptr1;
	}
	while (swapp);
}

//function to swap data of two nodes a and b
void swap(struct Node *a, struct Node *b)
{
	int temp = a->data;
	a->data = b->data;
	b->data = temp;
}

Output:

Linked list before sorting
9 8 2 56 32 11
Linked list after sorting
2 8 9 11 32 56

The time complexity of the above code is O(N2) as we doing nested traversals.

Now let us see C++ implementation. In C++ implementation we sort the linked list by swapping nodes.The bubble sort will be applied on nodes instead of values i.e.,we have to swap the nodes instead of values.So how to approach to this problem let's see.

Swap function:
In the swap() function, we will see how we can swap two adjacent nodes.

  1. Let the two adjacent nodes be p1 and p2.
  2. Now we will create 2 pointers ptr1 and ptr2, and will make ptr1 point to p1 and ptr2 point to p2.
  3. Next, we will create a pointer temp, and will make it point to the next of ptr2.
  4. We will make the next of ptr2 point to ptr1 and next of ptr1 point to temp.
  5. In this way, following the above steps, the two adjacent nodes p1 and p2 will get swapped.

Bubble sort function:
In this method, we will see how to perform Bubble Sort on the linked list.

  1. First, we need the count of the number of nodes in the list. The count can be found with a single list traversal.
  2. Now, the first loop is going to run from 0 to count-1.
  3. Inside the first loop, we will create a node pointer h that will point to the head and a variable swapped, initializing it with 0.
  4. The nested loop will run from 0 to count-i-1.
  5. Inside the nested loop, we will check if the adjacent elements are following ascending order or not.
    i. If any pair of adjacent nodes are not following the ascending order, we will swap the nodes and the value of swapped will become 1.
  6. After the above, if condition, we will increment the h.
  7. Now, after the inner loop, if the value of the variable swapped remains 0, it means that the list is sorted, and we will break the loop. Otherwise we will continue with the loop.

C++ implementation of Bubble Sort on Linked Lists:

#include <iostream>
using namespace std;

//structure of a node
class Node
{
    public:
    int data;
    Node *next;  //pointer to next node in singly linked list
};
//swap function
Node* swap(Node* ptr1, Node* ptr2)
{
    Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}

//bubblesort function
int bubbleSort(Node** head, int count)
{
    Node** h;
    int i, j, swapped;
  
    for (i = 0 ; i < count ; i++)
    {
  
        h = head;
        swapped = 0;
  
        for (j = 0 ; j < count  - i -1 ; j++) 
        {
  
            Node* p1 = *h;
            Node* p2 = p1->next;
  
            if (p1->data > p2->data)
            {

                *h = swap(p1, p2);
                swapped = 1;
            }
  
            h = &(*h)->next;
        }

        if (swapped == 0)
            break;
    }
}

void printList(Node* n)
{
    while (n != NULL)
    {
        cout << n->data << " -> ";
        n = n->next;
    }
    cout << endl;
}

void insertAtTheBegin(Node** start_ref, int data)
{
    Node* ptr1 = new Node;
  
    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}

int main()
{
    int arr[] = { 2,65,7,12,1 };
    int size, i;

    Node* head = NULL;
    size = sizeof(arr) / sizeof(arr[0]);

    for (i = 0; i < size; i++)
        insertAtTheBegin(&head, arr[i]);

    cout <<"Linked list before sorting\n";
    printList(head);

    bubbleSort(&head, size);

    cout <<"Linked list after sorting\n";
    printList(head);
  
    return 0;
}

Output:

Linked list before sorting
1 -> 12 -> 7 -> 65 -> 2 ->
Linked list after sorting
1 -> 2 -> 7 -> 12 -> 65 ->

The time complexity of the above code will be O(N2) as there are nested loops and traversal.

Now we will see how bubble sort works in doubly linked list the approach and method will be same just a small addition will be there.

Approach:As we do in the bubble sort, here we also have to check elements of two adjacent node whether they are in ascending order or not, if not then we swap the element. We do this until every element get its original position.In 1st pass the largest element get its original position and in 2nd pass 2nd largest element get its original position and in 3rd pass 3rd largest element get its original position and so on and finally whole list get sorted.

C++ implementation of bubble sort on doubly linked list:

//start of the code
#include <iostream>
using namespace std;

// structure of a node
class Node
{
    public:
    int data;
    Node* next; // Pointer to next node in doubly linked list
    Node* prev; // Pointer to previous node in doubly linked list
};
/* Function to insert a node at the beginning of a linked list */
void insertAtTheBegin(Node **start_ref, int data)
{
	Node *ptr1 = new Node;
	ptr1->data = data;
	ptr1->next = *start_ref;
	if (*start_ref != NULL)
	(*start_ref)->prev = ptr1;
	*start_ref = ptr1;
}

/* Function to print nodes in a given linked list */
void printList(Node *start)
{
	Node *temp = start;
	cout << endl;
	while (temp!=NULL)
	{
		cout << temp->data << " ";
		temp = temp->next;
	}
}

/* Bubble sort the given linked list */
void bubbleSort(Node *start)
{
	int swapped, i;
	Node *ptr1;
	Node *lptr = NULL;

	/* Checking for empty list */
	if (start == NULL)
		return;

	do
	{
		swapped = 0;
		ptr1 = start;

		while (ptr1->next != lptr)
		{
			if (ptr1->data > ptr1->next->data)
			{
				swap(ptr1->data, ptr1->next->data);
				swapped = 1;
			}
			ptr1 = ptr1->next;
		}
		lptr = ptr1;
	}
	while (swapped);
}

int main()
{
	int arr[] = {11,8,56,65,9,7};
	int i;

	/* start with empty linked list */
	struct Node *head = NULL;

	/* Create linked list from the array arr[]. */
	for (i = 0 ; i < 6 ; i++)
		insertAtTheBegin(&head, arr[i]);

	/* print list before sorting */
	printf("\n Linked list before sorting ");
	printList(head);

	/* sort the linked list */
	bubbleSort(head);

	/* print list after sorting */
	printf("\n Linked list after sorting ");
	printList(head);
	
	return 0;
}

Output:

Linked list before sorting
7 9 65 56 8 11
Linked list after sorting
7 8 9 11 56 65

This algorithm has several advantages. It is simple to write, easy to understand and it only takes a few lines of code. The data is sorted in place so there is little memory overhead and, once sorted, the data is in memory, ready for processing. The major disadvantage is the amount of time it takes to sort.

From all the above codes we can see that bubble sorting takes O(N2) time complexity which is good for small size linked lists but if the size is very large this technique is not useful.

So now I will conclude this topic as now you have a clear understanding of how bubble sorting technique works in a linked list whether it will be a singly linked list or a doubly linked list and we have also discussed about advantages and limitations of using bubble sorting technique.

Thank you.

—
Bubble Sort on Linked List
Share this