Bubble Sort On Doubly Linked List
Sort the given doubly linked list using bubble sort.
Examples:
Explanation
As we do in the bubble sort, here also we check elements of two adjacent node whether they are in ascending order or not, if not then we swap the element. We do this until every element get its original position.
In 1st pass the largest element get its original position and in 2nd pass 2nd largest element get its original position and in 3rd pass 3rd largest element get its original position and so on.
And finally whole list get sorted.
Note: If the list is already sorted then it will do only one pass.
C++
// CPP program to sort a doubly linked list using // bubble sort #include <iostream> using namespace std; // structure of a node struct Node { int data; Node* prev; Node* next; }; /* Function to insert a node at the beginning of a linked list */ void insertAtTheBegin(struct Node **start_ref, int data) { struct Node *ptr1 = new Node; ptr1->data = data; ptr1->next = *start_ref; if (*start_ref != NULL) (*start_ref)->prev = ptr1; *start_ref = ptr1; }
/* Function to print nodes in a given linked list */ void printList(struct Node *start) { struct Node *temp = start; cout << endl; while (temp!=NULL) { cout << temp->data << " "; temp = temp->next; } }
/* Bubble sort the given linked list */ void bubbleSort(struct Node *start) { int swapped, i; struct Node *ptr1; struct Node *lptr = NULL;
/* Checking for empty list */ if (start == NULL) return;
do { swapped = 0; ptr1 = start;
while (ptr1->next != lptr) { if (ptr1->data > ptr1->next->data) { swap(ptr1->data, ptr1->next->data); swapped = 1; } ptr1 = ptr1->next; } lptr = ptr1; } while (swapped); } int main() { int arr[] = {12, 56, 2, 11, 1, 90}; int list_size, i;
/* start with empty linked list */ struct Node *start = NULL;
/* Create linked list from the array arr[]. Created linked list will be 1->11->2->56->12 */ for (i = 0; i< 6; i++) insertAtTheBegin(&start, arr[i]);
/* print list before sorting */ printf("\n Linked list before sorting "); printList(start);
/* sort the linked list */ bubbleSort(start);
/* print list after sorting */ printf("\n Linked list after sorting "); printList(start);
return 0; } |
Java
// Java program to sort a doubly linked list using // bubble sort class GFG { // structure of a node static class Node { int data; Node prev; Node next; }; // Function to insert a node at the beginning of a linked list static Node insertAtTheBegin( Node start_ref, int data) { Node ptr1 = new Node(); ptr1.data = data; ptr1.next = start_ref; if (start_ref != null) (start_ref).prev = ptr1; start_ref = ptr1; return start_ref; } // Function to print nodes in a given linked list static void printList( Node start) { Node temp = start; System.out.println(); while (temp != null) { System.out.print( temp.data + " "); temp = temp.next; } } // Bubble sort the given linked list static Node bubbleSort( Node start) { int swapped, i; Node ptr1; Node lptr = null; // Checking for empty list if (start == null) return null; do { swapped = 0; ptr1 = start; while (ptr1.next != lptr) { if (ptr1.data > ptr1.next.data) { int t = ptr1.data; ptr1.data = ptr1.next.data; ptr1.next.data = t; swapped = 1; } ptr1 = ptr1.next; } lptr = ptr1; } while (swapped != 0); return start; } // Driver code public static void main(String args[]) { int arr[] = {12, 56, 2, 11, 1, 90}; int list_size, i; // start with empty linked list Node start = null; // Create linked list from the array arr[]. //Created linked list will be 1->11->2->56->12 for (i = 0; i < 6; i++) start=insertAtTheBegin(start, arr[i]); // print list before sorting System.out.printf("\n Linked list before sorting "); printList(start); // sort the linked list start = bubbleSort(start); // print list after sorting System.out.printf("\n Linked list after sorting "); printList(start); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to sort a doubly linked list using # bubble sort
# structure of a node class Node:
def __init__(self, data): self.data = data self.prev = None self.next = None
''' Function to insert a node at the beginning of a linked list ''' def insertAtTheBegin(start_ref, data): ptr1 = Node(data) ptr1.data = data; ptr1.next = start_ref; if (start_ref != None): (start_ref).prev = ptr1; start_ref = ptr1; return start_ref
''' Function to print nodes in a given linked list ''' def printList(start): temp = start; print() while (temp != None): print(temp.data, end = ' ') temp = temp.next;
''' Bubble sort the given linked list ''' def bubbleSort(start): swapped = 0 lptr = None;
''' Checking for empty list ''' if (start == None): return;
while True: swapped = 0; ptr1 = start; while (ptr1.next != lptr): if (ptr1.data > ptr1.next.data): ptr1.data, ptr1.next.data = ptr1.next.data, ptr1.data swapped = 1; ptr1 = ptr1.next; lptr = ptr1; if swapped == 0: break
# Driver code if __name__=='__main__':
arr = [12, 56, 2, 11, 1, 90]
''' start with empty linked list ''' start = None;
''' Create linked list from the array arr[]. Created linked list will be 1.11.2.56.12 ''' for i in range(6): start = insertAtTheBegin(start, arr[i]);
''' print list before sorting ''' print("Linked list before sorting ", end = ''); printList(start);
''' sort the linked list ''' bubbleSort(start);
''' print list after sorting ''' print("\nLinked list after sorting ", end = ''); printList(start);
# This code is contributed by rutvik_56 |
C#
// C# program to sort a doubly linked list using // bubble sort using System;
class GFG { // structure of a node public class Node { public int data; public Node prev; public Node next; }; // Function to insert a node at the beginning of a linked list static Node insertAtTheBegin( Node start_ref, int data) { Node ptr1 = new Node(); ptr1.data = data; ptr1.next = start_ref; if (start_ref != null) (start_ref).prev = ptr1; start_ref = ptr1; return start_ref; } // Function to print nodes in a given linked list static void printList( Node start) { Node temp = start; Console.WriteLine(); while (temp != null) { Console.Write( temp.data + " "); temp = temp.next; } } // Bubble sort the given linked list static Node bubbleSort( Node start) { int swapped; Node ptr1; Node lptr = null; // Checking for empty list if (start == null) return null; do { swapped = 0; ptr1 = start; while (ptr1.next != lptr) { if (ptr1.data > ptr1.next.data) { int t = ptr1.data; ptr1.data = ptr1.next.data; ptr1.next.data = t; swapped = 1; } ptr1 = ptr1.next; } lptr = ptr1; } while (swapped != 0); return start; } // Driver code public static void Main(String []args) { int []arr = {12, 56, 2, 11, 1, 90}; int i; // start with empty linked list Node start = null; // Create linked list from the array arr[]. //Created linked list will be 1->11->2->56->12 for (i = 0; i < 6; i++) start=insertAtTheBegin(start, arr[i]); // print list before sorting Console.Write("\n Linked list before sorting "); printList(start); // sort the linked list start = bubbleSort(start); // print list after sorting Console.Write("\n Linked list after sorting "); printList(start); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to sort a doubly linked list using // bubble sort // structure of a node class Node { constructor() { this.data = 0; this.next = null; this.prev = null; } } // Function to insert a node at the beginning of a linked list function insertAtTheBegin(start_ref, data) { var ptr1 = new Node(); ptr1.data = data; ptr1.next = start_ref; if (start_ref != null) start_ref.prev = ptr1; start_ref = ptr1; return start_ref; } // Function to print nodes in a given linked list function printList(start) { var temp = start; document.write("<br>"); while (temp != null) { document.write(temp.data + " "); temp = temp.next; } } // Bubble sort the given linked list function bubbleSort(start) { var swapped; var ptr1; var lptr = null; // Checking for empty list if (start == null) return null; do { swapped = 0; ptr1 = start; while (ptr1.next != lptr) { if (ptr1.data > ptr1.next.data) { var t = ptr1.data; ptr1.data = ptr1.next.data; ptr1.next.data = t; swapped = 1; } ptr1 = ptr1.next; } lptr = ptr1; } while (swapped != 0); return start; } // Driver code var arr = [12, 56, 2, 11, 1, 90]; var i; // start with empty linked list var start = null; // Create linked list from the array arr[]. //Created linked list will be 1->11->2->56->12 for (i = 0; i < 6; i++) start = insertAtTheBegin(start, arr[i]); // print list before sorting document.write("Linked list before sorting "); printList(start); // sort the linked list start = bubbleSort(start); // print list after sorting document.write("<br> Linked list after sorting "); printList(start);
// This code is contributed by rdtank. </script> |
Output: Linked list before sorting 90 1 11 2 56 12 Linked list after sorting 1 2 11 12 56 90
Article Tags :
Linked List
Sorting
BubbleSort
doubly linked list
Linked-List-Sorting
Practice Tags :
Linked List
Sorting
Read Full Article
bubble sort on doubly linked list in c++
C++ program for bubble sort on doubly linked list. Here problem description and explanation.
// Include header file #include <iostream> using namespace std; // C++ program for // Perform bubble sort in doubly linked list class LinkNode { public: int data; LinkNode *next; LinkNode *prev; LinkNode(int data) { this->data = data; this->next = nullptr; this->prev = nullptr; } }; class DoublyLinkedList { public: LinkNode *head; LinkNode *tail; DoublyLinkedList() { this->head = nullptr; this->tail = nullptr; } // Insert new node at end position void insert(int value) { // Create a node LinkNode *node = new LinkNode(value); if (this->head == nullptr) { // Add first node this->head = node; this->tail = node; return; } // Add node at last position this->tail->next = node; node->prev = this->tail; this->tail = node; } // Display node element of doubly linked list void display() { if (this->head == nullptr) { cout << "Empty Linked List" << endl; } else { cout << "\n Linked List Head to Tail :"; // Get first node of linked list LinkNode *temp = this->head; // iterate linked list while (temp != nullptr) { // Display node value cout << " " << temp->data; // Visit to next node temp = temp->next; } cout << "\n Linked List Tail to Head :"; // Get last node of linked list temp = this->tail; // iterate linked list while (temp != nullptr) { // Display node value cout << " " << temp->data; // Visit to prev node temp = temp->prev; } cout << "\n"; } } // Swap value of given node void swapData(LinkNode *first, LinkNode *second) { int value = first->data; first->data = second->data; second->data = value; } // Perform bubble sort void bubbleSort() { if (this->head == nullptr) { return; } bool task = true; // Get first node LinkNode *start = this->head; while (task == true) { task = false; while (start != nullptr && start->next != nullptr) { if (start->data > start->next->data) { this->swapData(start, start->next); // Active the next iteration task = true; } // Visit to next node start = start->next; } // Get first node start = this->head; } } }; int main() { DoublyLinkedList *dll = new DoublyLinkedList(); // Insert element of linked list dll->insert(5); dll->insert(3); dll->insert(7); dll->insert(1); dll->insert(9); dll->insert(6); dll->insert(2); dll->insert(8); dll->insert(-2); dll->insert(0); cout << " Before Sort "; // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL dll->display(); dll->bubbleSort(); cout << "\n After Sort"; //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL dll->display(); return 0; }Output
Before Sort Linked List Head to Tail : 5 3 7 1 9 6 2 8 -2 0 Linked List Tail to Head : 0 -2 8 2 6 9 1 7 3 5 After Sort Linked List Head to Tail : -2 0 1 2 3 5 6 7 8 9 Linked List Tail to Head : 9 8 7 6 5 3 2 1 0 -2Introduction to Linked List
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.It consists of nodes where each node contains a data field and a reference(link) to the next node in the list. There are many types of linked list:
- Singly linked list
- Doubly linked list
- Circular linked list
Introduction to Bubble Sort
Let's throw some light on Bubble sort that what is bubble sorting technique and how it works.It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.You will clearly understand how it works after seeing this below mentioned example.
Example:
First Pass:
( 6 1 5 3 8 ) –> ( 1 6 5 3 8 ), Here, algorithm compares the first two elements, and swaps since 6 > 1.
( 1 6 5 3 8 ) –> ( 1 5 6 3 8 ), Swap since 6 > 5
( 1 5 6 3 8 ) –> ( 1 5 3 6 8 ), Swap since 6 > 3
( 1 5 3 6 8 ) –> ( 1 5 3 6 8 ), Now, since these elements are already in order (8 > 6), algorithm does not swap them.
Second Pass:
( 1 5 3 6 8 ) –> ( 1 5 3 6 8 )
( 1 5 3 6 8 ) –> ( 1 3 5 6 8 ), Swap since 5 > 3
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
( 1 3 5 6 8 ) –> ( 1 3 5 6 8 )
Q. Program to sort the elements of the doubly linked list.
Explanation
In this program, we will create a doubly linked list and sort nodes of the list in ascending order.
Sorted List:
To accomplish this, we maintain two pointers: current and index. Initially, current point to head node and index will point to node next to current. Traverse through the list till current points to null, by comparing current's data with index's data. If the current's data is greater than the index's data, then swap data between them. In above example, current will initially point to 7, and the index will point to 1. Since, 7 is greater than 1, swap the data. Continue this process till the entire list is sorted in ascending order.
Algorithm
- Define a Node class which represents a node in the list. It will have three properties: data, previous which will point to the previous node and next which will point to the next node.
- Define another class for creating a doubly linked list, and it has two nodes: head and tail. Initially, head and tail will point to null.
- addNode() will add node to the list:
- It first checks whether the head is null, then it will insert the node as the head.
- Both head and tail will point to a newly added node.
- Head's previous pointer will point to null and tail's next pointer will point to null.
- If the head is not null, the new node will be inserted at the end of the list such that new node's previous pointer will point to tail.
- The new node will become the new tail. Tail's next pointer will point to null.
- sortList() will sort nodes of the list in ascending order.
- Define a node current which will point to head.
- Define another node index which will point to node next to current.
- Compare data of current and index node. If the current's data is greater than the index's data, then swap the data between them.
- Current will point to current.next and index will point to index.next.
- Continue this process till the entire list is sorted.
- display() will show all the nodes present in the list.
- Define a new node 'current' that will point to the head.
- Print current.data till current points to null.
- Current will point to the next node in the list in each iteration.