Bubble Sort On Doubly Linked List
Sort the given doubly linked list using bubble sort. Show ExplanationAs 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. C++
Java
Python3
C#
Javascript
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 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 ListA 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:
Introduction to Bubble SortLet'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: Second Pass: Third Pass: Q. Program to sort the elements of the doubly linked list.ExplanationIn 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
|
Doubly linked list bubble sort
Pos Terkait
Copyright © 2024 idkuu.com Inc.
