# Bubble Sort For a Linked List

Perform on Bubble sort in Given linked list, There are many possible solution of this problem.

Method 1: This is very simplest solution of this problem. compared the current node value to all other remaining nodes of linked list. When current node value is smaller then swap the node values by higher element. So this method is based on swapping node element values.

Suppose we are inserted the following (7, 50, 9, 42, 5, 15) node in a sequence.

Here given code implementation process.

Method 2: In this process use two linked list. One is form of given linked list and second is an empty linked list. Find largest node element to first linked list and separate this node and add to front of second linked list. Repeat this step until first linked list is not empty. Note that this is not actual bubble sort that is a way to achieve bubble sort.

``````//C Program
//By using get higher node
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
int data;
struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
void bubble_sort(struct Node**);
//insert Node element
//Create dynamic node
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL){
printf("Memory overflow\n");
}else{
node->data=value;
node->next=NULL;
}else{
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=node;
}
}
}
//Display element of Node
void display(struct Node*temp){

if(temp==NULL){
}
while(temp!=NULL){
printf("%d  ",temp->data);
temp=temp->next;
}
}
//perform bubble sort in single linked list

struct Node*current=NULL,
*move_node=NULL,
*prev=NULL;

prev=NULL;
while(current!=NULL){

//When current node value is grator than previous node
if(current->next!=NULL &&  current->next->data>move_node->data){
//Swap node values
move_node=current->next;
prev=current;

}
current=current->next;
}
}

if(prev!=NULL){
prev->next=move_node->next;
}
}

}else{
}
}
int main(){
//create node pointer

printf("Before sort : ");
//display all node

printf("\nAfter sort  : ");
return 0;
}``````

#### Output

``````Before sort : 7  50  9  42  5  15
After sort  : 5  7  9  15  42  50``````
``````//C++ Program
//By using get higher node
#include<iostream>
using namespace std;

//create structure
struct Node{
int data;
struct Node*next;
};
public:
void insert(int);
void display();
void bubble_sort();
};
}
//insert node at end of linked list
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow\n";
}else{
node->data=value;
node->next=NULL;
//base condition
}else{
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=node;
}
}
}
//display all node value in linked list
}
else{

while(temp!=NULL){
//print node value
cout<<temp->data<<"  ";
temp=temp->next;
}
}

}
//perform bubble sort in single linked list

Node*current=NULL,
*move_node=NULL,
*prev=NULL;

prev=NULL;
while(current!=NULL){

//When current node value is grator than previous node
if(current->next!=NULL &&  current->next->data>move_node->data){
//Swap node values
move_node=current->next;
prev=current;

}
current=current->next;
}
}

if(prev!=NULL){
prev->next=move_node->next;
}
}

}else{
}
}
int main(){

//create object
obj.insert(7);
obj.insert(50);
obj.insert(9);
obj.insert(42);
obj.insert(5);
obj.insert(15);
cout<<"Before sort : ";
//display all node
obj.display();

obj.bubble_sort();

cout<<"\nAfter sort  : ";
obj.display();
return 0;
}``````

#### Output

``````Before sort : 7  50  9  42  5  15
After sort  : 5  7  9  15  42  50``````
``````//Java Program
//By using get higher node

static class Node {
int data;
Node next;
}
//Class constructors
}
//insert element
public void insert(int value) {
//Create  node
Node node = new Node();
node.data = value;
node.next = null;
else {
//find last node
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}

}
public void display() {

while (temp != null) {
System.out.print("  " + temp.data);
temp = temp.next;
}
} else {
}
}
//perform bubble sort in single linked list
public void bubbleSort() {

Node current = null,
move_node = null,
prev = null;

prev = null;
while (current != null) {

//When current node value is grator than previous node
if (current.next != null && current.next.data > move_node.data) {
//Swap node values
move_node = current.next;
prev = current;

}
current = current.next;
}
}

if (prev != null) {
prev.next = move_node.next;
}
}

} else {
}
}

public static void main(String[] args) {

obj.insert(7);
obj.insert(50);
obj.insert(9);
obj.insert(42);
obj.insert(5);
obj.insert(15);
System.out.print("Before sort : ");

//display all node
obj.display();

obj.bubbleSort();
System.out.print("\nAfter sort  : ");

obj.display();
}
}``````

#### Output

``````Before sort :   7  50  9  42  5  15
After sort  :   5  7  9  15  42  50``````
``````#Python Program
#By using get higher node
class Node:
def __init__(self,data):
self.data=data
self.next=None

def __init__(self):
#Assign default value

#insert new node to linked list
def insert(self,data):
node=Node(data)
node.next=None
else:
while temp.next!=None:
temp=temp.next
temp.next=node

def display(self):
return

while(temp!=None):
print(temp.data,end=" ")
temp=temp.next

#perform bubble sort in single linked list
def bubbleSort(self):

current=None
move_node=None
prev=None

prev=None
while(current!=None):

#When current node value is grator than previous node
if(current.next!=None and  current.next.data>move_node.data):
#Swap node values
move_node=current.next
prev=current

current=current.next

if(prev!=None):
prev.next=move_node.next

else:

def main():
obj.insert(7)
obj.insert(50)
obj.insert(9)
obj.insert(42)
obj.insert(5)
obj.insert(15)
print("Before sort : ")

#display all node
obj.display()

obj.bubbleSort()
print("\nAfter sort  : ")

obj.display()
if __name__=="__main__":
main()``````

#### Output

``````Before sort :
7 50 9 42 5 15
After sort  :
5 7 9 15 42 50``````
``````//C# Program
//By using get higher node
using System;
//node class
public class Node{
public  int data;
public  Node next;
}
class Program
{
public Program(){
}
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
else{
//get last node
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
}
public void display(){
Console.Write("Empty List");
}else{
while(temp!=null){
Console.Write("  {0}",temp.data);
temp=temp.next;
}

}
}
//perform bubble sort in single linked list
public void bubbleSort(){

Node current = null,
move_node = null,
prev = null;

prev = null;
while (current != null) {

//When current node value is grator than previous node
if (current.next != null && current.next.data > move_node.data) {
//Swap node values
move_node = current.next;
prev = current;

}
current = current.next;
}
}

if (prev != null) {
prev.next = move_node.next;
}
}

}else{
}
}

static void Main()
{
Program obj=new Program();
obj.insert(7);
obj.insert(50);
obj.insert(9);
obj.insert(42);
obj.insert(5);
obj.insert(15);
Console.Write("Before sort : ");

//display all node
obj.display();

obj.bubbleSort();
Console.Write("\nAfter sort  : ");

obj.display();
}
}``````

#### Output

``````Before sort :   7  50  9  42  5  15
After sort  :   5  7  9  15  42  50``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.