Bubble Sort for Linked List by Swapping nodes
Given a singly linked list, sort it using bubble sort by swapping nodes.
Examples:
Input: 10->30->20->5
Output: 5->10->20->30Input: 20->4->3
Output: 3->4->20
Approach:
- Get the Linked List to be sorted
- Apply Bubble Sort to this linked list, in which, while comparing the two adjacent nodes, actual nodes are swapped instead of just swapping the data.
- Print the sorted list
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; // Structure for a node struct Node { int data; Node* next; }; // Function to swap the nodes Node* swap(Node* ptr1, Node* ptr2) { Node* tmp = ptr2->next; ptr2->next = ptr1; ptr1->next = tmp; return ptr2; } // Function to perform bubble sort on the linked list void 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) { // Update the link after swapping *h = swap(p1, p2); swapped = 1; } h = &(*h)->next; } // Break if the loop ended without any swap if (swapped == 0) break ; } } // Function to print the linked list void printList(Node* n) { while (n != nullptr) { cout << n->data << " -> " ; n = n->next; } cout << endl; } // Function to insert a node at the beginning of the linked list void insertAtTheBegin(Node** start_ref, int data) { Node* ptr1 = new Node; ptr1->data = data; ptr1->next = *start_ref; *start_ref = ptr1; } // Driver Code int main() { int arr[] = {78, 20, 10, 32, 1, 5}; int list_size, i; // Start with an empty linked list Node* start = nullptr; list_size = sizeof (arr) / sizeof (arr[0]); // Create linked list from the array arr[] for (i = 0; i < list_size; i++) insertAtTheBegin(&start, arr[i]); // Print list before sorting cout << "Linked list before sorting" << endl; printList(start); // Sort the linked list using bubble sort bubbleSort(&start, list_size); // Print list after sorting cout << "Linked list after sorting" << endl; printList(start); return 0; } |
C
// C program to sort Linked List // using Bubble Sort // by swapping nodes #include <stdio.h> #include <stdlib.h> /* structure for a node */ struct Node { int data; struct Node* next; } Node; /*Function to swap the nodes */ struct Node* swap( struct Node* ptr1, struct Node* ptr2) { struct Node* tmp = ptr2->next; ptr2->next = ptr1; ptr1->next = tmp; return ptr2; } /* Function to sort the list */ int bubbleSort( struct Node** head, int count) { struct Node** h; int i, j, swapped; for (i = 0; i <= count; i++) { h = head; swapped = 0; for (j = 0; j < count - i - 1; j++) { struct Node* p1 = *h; struct Node* p2 = p1->next; if (p1->data > p2->data) { /* update the link after swapping */ *h = swap(p1, p2); swapped = 1; } h = &(*h)->next; } /* break if the loop ended without any swap */ if (swapped == 0) break ; } } /* Function to print the list */ void printList( struct Node* n) { while (n != NULL) { printf ( "%d -> " , n->data); n = n->next; } printf ( "\n" ); } /* Function to insert a struct 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; } // Driver Code int main() { int arr[] = { 78, 20, 10, 32, 1, 5 }; int list_size, i; /* start with empty linked list */ struct Node* start = NULL; list_size = sizeof (arr) / sizeof (arr[0]); /* Create linked list from the array arr[] */ for (i = 0; i < list_size; i++) insertAtTheBegin(&start, arr[i]); /* print list before sorting */ printf ( "Linked list before sorting\n" ); printList(start); /* sort the linked list */ bubbleSort(&start, list_size); /* print list after sorting */ printf ( "Linked list after sorting\n" ); printList(start); return 0; } |
Java
// Java Program to sort a linked list // using bubble sort by swapping nodes // Node class class Node { int data; Node next; // Constructor to initialize the node object public Node( int data) { this .data = data; this .next = null ; } } // LinkedList class class LinkedList { Node head; // Function to swap nodes x and y in linked list by changing links public void swapNodes( int x, int y) { // Nothing to do if x and y are the same if (x == y) { return ; } // Search for x (keep track of prevX and currX) Node prevX = null , currX = head; while (currX != null && currX.data != x) { prevX = currX; currX = currX.next; } // Search for y (keep track of prevY and currY) Node prevY = null , currY = head; while (currY != null && currY.data != y) { prevY = currY; currY = currY.next; } // If either x or y is not present, nothing to do if (currX == null || currY == null ) { return ; } // If x is not head of linked list if (prevX != null ) { prevX.next = currY; } else { // Else make y as new head head = currY; } // If y is not head of linked list if (prevY != null ) { prevY.next = currX; } else { // Else make x as new head head = currX; } // Swap next pointers Node temp = currX.next; currX.next = currY.next; currY.next = temp; } // Function to sort the linked list using bubble sort public void bubbleSort() { if (head == null ) { return ; } int count = 0 ; Node start = head; while (start != null ) { count++; start = start.next; } // Traverse through all nodes of linked list for ( int i = 0 ; i < count; i++) { // Last i elements are already in place Node curr = head; while (curr != null && curr.next != null ) { // Swap adjacent nodes if (curr.data > curr.next.data) { swapNodes(curr.data, curr.next.data); } curr = curr.next; } } } // Function to print the linked list public void printList() { Node tmp = head; while (tmp != null ) { System.out.print(tmp.data + " -> " ); tmp = tmp.next; } System.out.println( "None" ); } } // Driver Code public class Main { public static void main(String[] args) { int [] arr = { 78 , 20 , 10 , 32 , 1 , 5 }; // Create a linked list from the array LinkedList llist = new LinkedList(); llist.head = new Node(arr[ 0 ]); Node start = llist.head; for ( int i = 1 ; i < arr.length; i++) { start.next = new Node(arr[i]); start = start.next; } // Print the list before sorting System.out.println( "Linked list before sorting" ); llist.printList(); // Sort the list llist.bubbleSort(); // Print the list after sorting System.out.println( "Linked list after sorting" ); llist.printList(); } } |
Python3
# Python Program to sort a linked list # using bubble sort by swapping nodes # Node class class Node: # Constructor to initialize the node object def __init__( self , data): self .data = data self . next = None class LinkedList: # Function to initialize head def __init__( self ): self .head = None # Function to swap nodes x and y in linked list by # changing links def swapNodes( self , x, y): # Nothing to do if x and y are same if x = = y: return # Search for x (keep track of prevX and CurrX) prevX = None currX = self .head while currX ! = None and currX.data ! = x: prevX = currX currX = currX. next # Search for y (keep track of prevY and currY) prevY = None currY = self .head while currY ! = None and currY.data ! = y: prevY = currY currY = currY. next # If either x or y is not present, nothing to do if currX = = None or currY = = None : return # If x is not head of linked list if prevX ! = None : prevX. next = currY else : # Else make y as new head self .head = currY # If y is not head of linked list if prevY ! = None : prevY. next = currX else : # Else make x as new head self .head = currX # Swap next pointers temp = currX. next currX. next = currY. next currY. next = temp # Function to sort the linked list using bubble sort def bubbleSort( self ): count = 0 start = self .head while start ! = None : count + = 1 start = start. next # Traverse through all nodes of linked list for i in range ( 0 , count): # Last i elements are already in place start = self .head while start ! = None : # Swap adjacent nodes ptr = start. next if ptr ! = None : if start.data > ptr.data: self .swapNodes(start.data, ptr.data) start = start. next # Function to print the linked list def printList( self ): tmp = self .head while tmp ! = None : print (tmp.data, end = " -> " ) tmp = tmp. next print ( "None" ) # Driver Code if __name__ = = '__main__' : arr = [ 78 , 20 , 10 , 32 , 1 , 5 ] # Create a linked list from array llist = LinkedList() llist.head = Node(arr[ 0 ]) start = llist.head for i in range ( 1 , len (arr)): start. next = Node(arr[i]) start = start. next # Print the list before sorting print ( "Linked list before sorting" ) llist.printList() # Sort the list llist.bubbleSort() # Print the list after sorting print ( "Linked list after sorting" ) llist.printList() |
C#
using System; // Node class class Node { public int data; public Node next; // Constructor to initialize the node object public Node( int data) { this .data = data; this .next = null ; } } // LinkedList class class LinkedList { public Node head; // Function to swap nodes x and y in linked list by changing links public void SwapNodes( int x, int y) { // Nothing to do if x and y are the same if (x == y) { return ; } // Search for x (keep track of prevX and currX) Node prevX = null , currX = head; while (currX != null && currX.data != x) { prevX = currX; currX = currX.next; } // Search for y (keep track of prevY and currY) Node prevY = null , currY = head; while (currY != null && currY.data != y) { prevY = currY; currY = currY.next; } // If either x or y is not present, nothing to do if (currX == null || currY == null ) { return ; } // If x is not head of linked list if (prevX != null ) { prevX.next = currY; } else { // Else make y as new head head = currY; } // If y is not head of linked list if (prevY != null ) { prevY.next = currX; } else { // Else make x as new head head = currX; } // Swap next pointers Node temp = currX.next; currX.next = currY.next; currY.next = temp; } // Function to sort the linked list using bubble sort public void BubbleSort() { if (head == null ) { return ; } int count = 0; Node start = head; while (start != null ) { count++; start = start.next; } // Traverse through all nodes of linked list for ( int i = 0; i < count; i++) { // Last i elements are already in place Node curr = head; while (curr != null && curr.next != null ) { // Swap adjacent nodes if (curr.data > curr.next.data) { SwapNodes(curr.data, curr.next.data); } curr = curr.next; } } } // Function to print the linked list public void PrintList() { Node tmp = head; while (tmp != null ) { Console.Write(tmp.data + " -> " ); tmp = tmp.next; } Console.WriteLine( "None" ); } } // Driver class public class LinkedListMain { public static void Main( string [] args) { int [] arr = { 78, 20, 10, 32, 1, 5 }; // Create a linked list from the array LinkedList llist = new LinkedList(); llist.head = new Node(arr[0]); Node start = llist.head; for ( int i = 1; i < arr.Length; i++) { start.next = new Node(arr[i]); start = start.next; } // Print the list before sorting Console.WriteLine( "Linked list before sorting" ); llist.PrintList(); // Sort the list llist.BubbleSort(); // Print the list after sorting Console.WriteLine( "Linked list after sorting" ); llist.PrintList(); } } //This code is contributed by Aman |
Javascript
// Javascript program for the above approach // Node class class Node { // Constructor to initialize the node object constructor(data) { this .data = data; this .next = null ; } } class LinkedList { // Function to initialize head constructor() { this .head = null ; } // Function to swap nodes x and y in linked list by changing links swapNodes(x, y) { // Nothing to do if x and y are same if (x === y) { return ; } // Search for x (keep track of prevX and CurrX) let prevX = null ; let currX = this .head; while (currX !== null && currX.data !== x) { prevX = currX; currX = currX.next; } // Search for y (keep track of prevY and currY) let prevY = null ; let currY = this .head; while (currY !== null && currY.data !== y) { prevY = currY; currY = currY.next; } // If either x or y is not present, nothing to do if (currX === null || currY === null ) { return ; } // If x is not head of linked list if (prevX !== null ) { prevX.next = currY; } else { // Else make y as new head this .head = currY; } // If y is not head of linked list if (prevY !== null ) { prevY.next = currX; } else { // Else make x as new head this .head = currX; } // Swap next pointers let temp = currX.next; currX.next = currY.next; currY.next = temp; } // Function to sort the linked list using bubble sort bubbleSort() { let count = 0; let start = this .head; while (start !== null ) { count++; start = start.next; } // Traverse through all nodes of linked list for (let i = 0; i < count; i++) { // Last i elements are already in place start = this .head; while (start !== null ) { // Swap adjacent nodes let ptr = start.next; if (ptr !== null ) { if (start.data > ptr.data) { this .swapNodes(start.data, ptr.data); } } start = start.next; } } } // Function to print the linked list printList() { let store = []; let tmp = this .head; while (tmp !== null ) { store.push(tmp.data); store.push( " ->" ); // console.log(tmp.data + " -> "); tmp = tmp.next; } store.push( "None" ); console.log(store.join( " " )) } } // Driver Code let arr = [78, 20, 10, 32, 1, 5]; // Create a linked list from array let llist = new LinkedList(); llist.head = new Node(arr[0]); let start = llist.head; for (let i = 1; i < arr.length; i++) { start.next = new Node(arr[i]); start = start.next; } // Print the list before sorting console.log( "Linked list before sorting" ); llist.printList(); // Sort the list llist.bubbleSort(); console.log( "Linked List After Sorting" ); llist.printList(); // This code is contributed by princekumaras |
Output
Linked list before sorting 5 -> 1 -> 32 -> 10 -> 20 -> 78 -> Linked list after sorting 1 -> 5 -> 10 -> 20 -> 32 -> 78 ->
Time complexity: O(N^2), where N is the number of nodes in the Linked List.
Auxiliary space: O(1)