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)