One easier way is just to copy the data of the node, you can swap the data but the pointer to the node. if(current->number > current->next->number){ swap(current->id,current->next->id); swap(current->name,current->next->name); swap(current->number,current->next->number); }With your method, you never set the previous pointer at all. You can sort the double linked list as single list at first, and then traversal the list again to set all the prev pointer. Of course, you can sort the double linked list at a time, but it's a little complex to implement. You should consider 4 nodes each step, i.e current, current->next, as well as current->prev and current->next->next. When you want to swap current and current->next, you should set current->prev->next=current->next, current->next=current->next->next so on and so forth. In this article, we have presented the approach to implement Bubble Sort on Singly Linked List and Doubly Linked List along with implementations in C and C++. Table of contents:
Prerequisite: Linked List, Bubble Sort 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:
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: ( 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 ) Now let's talk about how this technique works in linked list. Given a linked list and we have to sort it using bubble sort method.Let's see what will be the steps involved or you can say passes in this technique to sort a given linked list. Approach:First we have to form a linked list by inserting the values one by one and after insertion first we will point a head pointer towards the first node and keep on checking whether the current node data where the pointer is currently present is smaller,bigger or equal to the next node value. If the current node value is smaller or equal to next node value we will move our pointer further and point it towards the next node but if the current node value is bigger as compared to the next node value then we will swap the nodes with each other and make our pointer point towards the next node or that node which is swapped recently and keep on performing these passes until we will get the sorted list. Input: 12->35->2->67 Now we have to sort this list we have inserted the node values and now we start traversing the given list. First pass: (12->35->2->67) => (12->35->2->67) as our pointer is pointing at 12(bolder part) and after comparing it with next node value we can see that 35>12 so we will not do anything just simply move our pointer point towards next node i.e, 35. (12->35->2->67) => (12->2->35->67) now 35>2 so we will swap the adjacent nodes and move our pointer at third node which is again 35. (12->2->35->67) => (12->2->35->67) as our pointer is pointing at 35(bolder part) and after comparing it with next node value we can see that 67>35 so we will not do anything just simply move our pointer point towards next node i.e, 67. Now there is no node value next to the current node so we will move to the second pass. Second pass: Third pass: Now after having a clear understanding of how bubble sorting on linked list works we will write code for this in both C and in C++. C implementation of Bubble Sort on Linked List: // C program to implement Bubble Sort on singly linked list #include<stdio.h> #include<stdlib.h> //structure of a node struct Node { int data; //value of a node struct Node *next; }; //Function to insert a node at the beginning of a linked list void insertAtTheBegin(struct Node **start_ref, int data); //Function to bubble sort the given linked list void bubbleSort(struct Node *start); //Function to swap data of two nodes a and b void swap(struct Node *a, struct Node *b); //Function to print nodes in a given linked list void printList(struct Node *start); int main() { int a[] = {11,32,56,2,8,9}; int size, i; struct Node *head = NULL; for (i = 0; i< 6; i++) insertAtTheBegin(&head, a[i]); //function calling for inserting elements //print list before sorting printf("\n Linked list before sorting "); printList(head); //sort the linked list bubbleSort(head); //print list after sorting printf("\n Linked list after sorting "); printList(head); getchar(); return 0; } //Function to insert a 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; } //Function to print nodes in a given linked list void printList(struct Node *start) { struct Node *temp = start; printf("\n"); while (temp!=NULL) { printf("%d ", temp->data); temp = temp->next; } } //Bubble sort the given linked list void bubbleSort(struct Node *head) { int swapp, i; struct Node *ptr1; struct Node *lptr = NULL; /* Checking for empty list */ if (head == NULL) return; do { swapp = 0; ptr1 = head; while (ptr1->next != lptr) { if (ptr1->data > ptr1->next->data) { swap(ptr1, ptr1->next); swapp = 1; } ptr1 = ptr1->next; } lptr = ptr1; } while (swapp); } //function to swap data of two nodes a and b void swap(struct Node *a, struct Node *b) { int temp = a->data; a->data = b->data; b->data = temp; }Output: Linked list before sorting 9 8 2 56 32 11 Linked list after sorting 2 8 9 11 32 56The time complexity of the above code is O(N2) as we doing nested traversals. Now let us see C++ implementation. In C++ implementation we sort the linked list by swapping nodes.The bubble sort will be applied on nodes instead of values i.e.,we have to swap the nodes instead of values.So how to approach to this problem let's see. Swap function:
Bubble sort function:
C++ implementation of Bubble Sort on Linked Lists: #include <iostream> using namespace std; //structure of a node class Node { public: int data; Node *next; //pointer to next node in singly linked list }; //swap function Node* swap(Node* ptr1, Node* ptr2) { Node* tmp = ptr2->next; ptr2->next = ptr1; ptr1->next = tmp; return ptr2; } //bubblesort function int 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) { *h = swap(p1, p2); swapped = 1; } h = &(*h)->next; } if (swapped == 0) break; } } void printList(Node* n) { while (n != NULL) { cout << n->data << " -> "; n = n->next; } cout << endl; } void insertAtTheBegin(Node** start_ref, int data) { Node* ptr1 = new Node; ptr1->data = data; ptr1->next = *start_ref; *start_ref = ptr1; } int main() { int arr[] = { 2,65,7,12,1 }; int size, i; Node* head = NULL; size = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < size; i++) insertAtTheBegin(&head, arr[i]); cout <<"Linked list before sorting\n"; printList(head); bubbleSort(&head, size); cout <<"Linked list after sorting\n"; printList(head); return 0; }Output: Linked list before sorting 1 -> 12 -> 7 -> 65 -> 2 -> Linked list after sorting 1 -> 2 -> 7 -> 12 -> 65 ->The time complexity of the above code will be O(N2) as there are nested loops and traversal. Now we will see how bubble sort works in doubly linked list the approach and method will be same just a small addition will be there. Approach:As we do in the bubble sort, here we also have to 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. C++ implementation of bubble sort on doubly linked list: //start of the code #include <iostream> using namespace std; // structure of a node class Node { public: int data; Node* next; // Pointer to next node in doubly linked list Node* prev; // Pointer to previous node in doubly linked list }; /* Function to insert a node at the beginning of a linked list */ void 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; } /* Function to print nodes in a given linked list */ void printList(Node *start) { Node *temp = start; cout << endl; while (temp!=NULL) { cout << temp->data << " "; temp = temp->next; } } /* Bubble sort the given linked list */ void bubbleSort(Node *start) { int swapped, i; Node *ptr1; 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[] = {11,8,56,65,9,7}; int i; /* start with empty linked list */ struct Node *head = NULL; /* Create linked list from the array arr[]. */ for (i = 0 ; i < 6 ; i++) insertAtTheBegin(&head, arr[i]); /* print list before sorting */ printf("\n Linked list before sorting "); printList(head); /* sort the linked list */ bubbleSort(head); /* print list after sorting */ printf("\n Linked list after sorting "); printList(head); return 0; }Output: Linked list before sorting 7 9 65 56 8 11 Linked list after sorting 7 8 9 11 56 65This algorithm has several advantages. It is simple to write, easy to understand and it only takes a few lines of code. The data is sorted in place so there is little memory overhead and, once sorted, the data is in memory, ready for processing. The major disadvantage is the amount of time it takes to sort. From all the above codes we can see that bubble sorting takes O(N2) time complexity which is good for small size linked lists but if the size is very large this technique is not useful. So now I will conclude this topic as now you have a clear understanding of how bubble sorting technique works in a linked list whether it will be a singly linked list or a doubly linked list and we have also discussed about advantages and limitations of using bubble sorting technique. Thank you. |