DAA: Bubble Sort Algorithm on Linked List

Bubble Sort Algorithm on Linked List

In this article, we will sort a Link List using the bubble sort technique.

Example:

Input : 20->30->40->10

Output :10->20->30->40

Input : 20->4->3

Output : 3->4->20

Sorting Technique

The bubble sort technique works similarly as it takes two adjacent elements, compares them and the swaps the smaller one with larger one. At the end of pass 1, the largest element reaches its final position.

C Code:

 #include <stdio.h>
 #include <malloc.h>
 /* Link list node */
 typedef struct node {
     int data;
     struct node* next;
 } node;
 node* head = NULL;
 /*Function to create a linked list*/
 void createll()
 {
     int i, n;
     node* tail; // keeps track of the last element
     tail = head; //atm head is the last element
     int arr[4] = { 20, 30, 40, 10};
     for (i = 0; i < 4; i++) {
         node* newn;
         newn = (node*)malloc(sizeof(node)); //creates a new node in every iteration
         newn->data = arr[i];
         newn->next = NULL;
         if (head == NULL) {
             head = newn;
             tail = head;
         }
         else {
             tail->next = newn; //linking the previous last element to new last element
             tail = newn; //making the new element as the last element
         }
     }
 }
 /* Function to print linked list */
 void display()
 {
     struct node* temp = head;
     while (temp != NULL) {
         printf("%d  ", temp->data);
         temp = temp->next;
     }
     printf("\n");
 }
 /* function to swap data of two nodes a and b*/
 void swap(node* a, node* b)
 {
     int temp = a->data;
     a->data = b->data;
     b->data = temp;
 }
 /*Function to bubble sort*/
 void bubble()
 {
     int ctr, n = 1;
     node *t1, *t2;
     t1 = head;
     do {
         ctr = 0;
         t2 = head;
         while (t2->next != NULL) {
             if (t2->data > t2->next->data) {
                 swap(t2, t2->next);
                 ctr = 1;
             }
             t2 = t2->next;
         }
         t1 = t1->next;
         n++;
     } while (t1->next != NULL && ctr);
 }
 void main()
 {
     createll();
     printf("Before Sorting: ");
     display();
     bubble();
     printf("\nAfter Sorting: ");
     display();
 } 

C++ Code:

 #include <iostream>
 using namespace std;
 struct node {
     int data;
     node* next;
 }* head = NULL;
 bool Is_List_Empty()
 {
     if (head == NULL)
         return true;
     return false;
 }
 void Insert_At_End(int value)
 {
     node *temp = new node, *current = head;
     temp->data = value;
     temp->next = NULL;
     if (Is_List_Empty()) {
         head = temp;
         return;
     }
     while (current->next != NULL)
         current = current->next;
     current->next = temp;
 }
 void Bubble_Sort()
 {
     int cnt = 0;
     node* start = head;
     node* curr = NULL;
     node* trail = NULL;
     node* tmp = NULL;
     //get cnt(size) of linked list
     while (start != NULL) {
         start = start->next;
         ++cnt;
     }
     for (int i = 0; i < cnt; ++i) {
         //set curr and trail at the start node
         curr = trail = head;
         while (curr->next != NULL) {
             //compares curr and its next
             if (curr->data > curr->next->data) {
                 //swaps pointers for curr & curr->next
                 tmp = curr->next;
                 curr->next = curr->next->next;
                 tmp->next = curr;
                 //setup pointers for the head and trail if applicable
                 if (curr == head)
                     head = trail = tmp;
                 else
                     trail->next = tmp;
                 curr = tmp;
             }
             //advance pointers
             trail = curr;
             curr = curr->next;
         }
     }
 }
 void Print_Linked_List()
 {
     if (Is_List_Empty()) {
         cout << "List is Empty" << endl;
         return;
     }
     node* current = head;
     while (current->next != NULL) {
         cout << current->data << " ";
         current = current->next;
     }
     cout << current->data << endl;
 }
 int main()
 {
     int i;
     cout << "Before sorting: ";
     int arr[4] = { 20, 30, 40, 10 };
     for (i = 0; i < 4; i++)
         Insert_At_End(arr[i]);
     Print_Linked_List();
     Bubble_Sort();
     cout << "After sorting: ";
     Print_Linked_List();
     return 0;
 } 

Java Code:

 public
 class Linked_List_Bubble_Sort {
 public
     static void main(String[] args)
     {
         LinkedList list = new LinkedList();
         // Adding integers unordered
         list.insertAtTop(10);
         list.insertAtTop(40);
         list.insertAtTop(30);
         list.insertAtTop(20);
         // Prints the integers before sorting
         System.out.print("Before sorting: ");
         list.print();
         // Call BubbleSort method
         list.bubbleSort();
         // Prints out the integers after sorting
         System.out.print("After sorting: ");
         list.print();
     }
     static class Node {
     private
         int item;
     private
         Node next;
         // Constructor
     public
         Node(int newItem, Node newNode)
         {
             item = newItem;
             next = newNode;
         }
         // Getter's and Setters
     public
         int getItem()
         {
             return item;
         }
     public
         void setItem(int newItem)
         {
             item = newItem;
         }
     public
         Node getNext()
         {
             return next;
         }
     public
         void setNext(Node newNext)
         {
             next = newNext;
         }
     }
     static class LinkedList {
     private
         Node top;
     public
         LinkedList()
         {
             top = null;
         }
     public
         void insertAtTop(int value)
         {
             Node newNode = new Node(value, top);
             top = newNode;
         }
     public
         void print()
         {
             Node curr = top;
             while (curr != null) {
                 System.out.print(curr.getItem() + " ");
                 curr = curr.getNext();
             }
             System.out.println();
         }
     public
         void bubbleSort()
         {
             Node curr = top;
             Node prev = null;
             int temp = 0;
             while (curr.getNext() != null) {
                 prev = top;
                 while (prev.getNext() != null) {
                     // If previous item is greater than current
                     if (prev.getItem() > prev.getNext().getItem()) {
                         temp = prev.getItem();
                         // Make the swap
                         prev.setItem(prev.getNext().getItem());
                         prev.getNext().setItem(temp);
                     }
                     prev = prev.getNext();
                 }
                 curr = curr.getNext();
             }
         }
     }
 } 

Output:

 Before sorting: 20 30 40 10
 After sorting: 10 20 30 40 

Time complexity: O(n*n)