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.
-
1) Bubble sort on linked list in java
2) Bubble sort on linked list in c++
3) Bubble sort on linked list in golang
4) Bubble sort of linked list in c
5) Bubble sort on linked list in c#
6) Bubble sort on linked list in vb.net
7) Bubble sort on linked list in php
8) Bubble sort on linked list in node js
9) Bubble sort on linked list in typescript
10) Bubble sort on linked list in python
11) Bubble sort on linked list in ruby
12) Bubble sort on linked list in scala
13) Bubble sort on linked list in swift
14) Bubble sort on linked list in kotlin
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
//Bubble Sort For Linked List
//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
void insert(struct Node**head,int value){
//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;
if(*head==NULL){
*head=node;
}else{
struct Node*temp=*head;
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
//add node at last possition
temp->next=node;
}
}
}
//Display element of Node
void display(struct Node*temp){
if(temp==NULL){
printf("Empty linked list");
}
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->next;
}
}
//perform bubble sort in single linked list
void bubble_sort(struct Node**head){
if(*head!=NULL){
struct Node*current=NULL,
*new_head=NULL,
*move_node=NULL,
*prev=NULL;
while(*head!=NULL){
prev=NULL;
current=*head;
move_node=*head;
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(move_node==*head){
*head=(*head)->next;
}
if(prev!=NULL){
prev->next=move_node->next;
}
move_node->next=new_head;
new_head=move_node;
}
//make new head
*head=new_head;
}else{
printf("Empty linked list");
}
}
int main(){
//create node pointer
struct Node*head=NULL;
//insert element of linked list
insert(&head,7);
insert(&head,50);
insert(&head,9);
insert(&head,42);
insert(&head,5);
insert(&head,15);
printf("Before sort : ");
//display all node
display(head);
bubble_sort(&head);
printf("\nAfter sort : ");
display(head);
return 0;
}Output
Before sort : 7 50 9 42 5 15
After sort : 5 7 9 15 42 50//C++ Program
//Bubble Sort For Linked List
//By using get higher node
#include<iostream>
using namespace std;
//create structure
struct Node{
int data;
struct Node*next;
};
class LinkedList{
Node*head;//head node
public:
LinkedList();
void insert(int);
void display();
void bubble_sort();
};
LinkedList::LinkedList(){
head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value){
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow\n";
}else{
node->data=value;
node->next=NULL;
if(head==NULL){
//base condition
head=node;
}else{
Node*temp=head;
while(temp->next!=NULL){
temp=temp->next;
}
//add newly node at last
temp->next=node;
}
}
}
//display all node value in linked list
void LinkedList:: display(){
if(head==NULL){
cout<<"Empty linked list";
}
else{
Node*temp=head;
while(temp!=NULL){
//print node value
cout<<temp->data<<" ";
temp=temp->next;
}
}
}
//perform bubble sort in single linked list
void LinkedList:: bubble_sort(){
if(head!=NULL){
Node*current=NULL,
*new_head=NULL,
*move_node=NULL,
*prev=NULL;
while(head!=NULL){
prev=NULL;
current=head;
move_node=head;
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(move_node==head){
head=(head)->next;
}
if(prev!=NULL){
prev->next=move_node->next;
}
move_node->next=new_head;
new_head=move_node;
}
//make new head
head=new_head;
}else{
cout<<"Empty linked list"<<endl;
}
}
int main(){
//create object
LinkedList obj;
//insert element of linked list
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
//Bubble Sort For Linked List
//By using get higher node
public class LinkedList {
static class Node {
int data;
Node next;
}
public Node head;
//Class constructors
LinkedList() {
head = null;
}
//insert element
public void insert(int value) {
//Create node
Node node = new Node();
node.data = value;
node.next = null;
if (head == null) head = node;
else {
Node temp = head;
//find last node
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
//Display all Linked List elements
public void display() {
if (head != null) {
Node temp = head;
while (temp != null) {
System.out.print(" " + temp.data);
temp = temp.next;
}
} else {
System.out.println("Empty Linked list");
}
}
//perform bubble sort in single linked list
public void bubbleSort() {
if (head != null) {
Node current = null,
new_head = null,
move_node = null,
prev = null;
while (head != null) {
prev = null;
current = head;
move_node = head;
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 (move_node == head) {
head = (head).next;
}
if (prev != null) {
prev.next = move_node.next;
}
move_node.next = new_head;
new_head = move_node;
}
//make new head
head = new_head;
} else {
System.out.println("Empty Linked list");
}
}
public static void main(String[] args) {
LinkedList obj = new LinkedList();
//insert element of linked list
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
#Bubble Sort For Linked List
#By using get higher node
class Node:
def __init__(self,data):
self.data=data
self.next=None
#Create Class Linked
class Linked:
def __init__(self):
#Assign default value
self.head=None
#insert new node to linked list
def insert(self,data):
node=Node(data)
node.next=None
if self.head==None:
self.head=node
else:
temp=self.head
while temp.next!=None:
temp=temp.next
#add node
temp.next=node
def display(self):
if(self.head==None):
print("Empty Linked List")
return
temp=self.head
while(temp!=None):
print(temp.data,end=" ")
temp=temp.next
#perform bubble sort in single linked list
def bubbleSort(self):
if(self.head!=None):
current=None
new_head=None
move_node=None
prev=None
while(self.head!=None):
prev=None
current=self.head
move_node=self.head
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(move_node==self.head):
self.head=(self.head).next
if(prev!=None):
prev.next=move_node.next
move_node.next=new_head
new_head=move_node
#make new head
self.head=new_head
else:
print("Empty Linked list")
def main():
#Create Object of class Linked
obj=Linked()
#insert element of linked list
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
//Bubble Sort For Linked List
//By using get higher node
using System;
//node class
public class Node{
public int data;
public Node next;
}
class Program
{
Node head;
public Program(){
head=null;
}
//insert node of linked list
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
if(head==null) head=newNode;
else{
Node temp=head;
//get last node
while(temp.next!=null){
temp=temp.next;
}
//add new node
temp.next=newNode;
}
}
//display linked list nodes value
public void display(){
if(head==null){
Console.Write("Empty List");
}else{
Node temp=head;
while(temp!=null){
Console.Write(" {0}",temp.data);
temp=temp.next;
}
}
}
//perform bubble sort in single linked list
public void bubbleSort(){
if(head!=null){
Node current = null,
new_head = null,
move_node = null,
prev = null;
while (head != null) {
prev = null;
current = head;
move_node = head;
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 (move_node == head) {
head = (head).next;
}
if (prev != null) {
prev.next = move_node.next;
}
move_node.next = new_head;
new_head = move_node;
}
//make new head
head = new_head;
}else{
Console.WriteLine("Empty Linked list");
}
}
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
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.
New Comment