Bubble Sort On Linked List
“Bubble Sort On Linked List” is one of the basic problem based on the linked list data structure and sorting algorithm. Here, we are given a linked list and our task is sort the elements of given linked list in ascending order using bubble sort.
Example:
Linked List Before Sorting: Linked List: 19 -> 17 -> 15 -> 18 -> 16 Linked List After Sorting: Linked List: 15 -> 16 -> 17 -> 18 -> 19
C++ Program to perform bubble sort on linked list is as follows:
/* C++ Program to perform bubble sort on linked list */ #include<iostream> using namespace std; /* Structure of Node of the Linked List */ struct node { int data; struct node *next; }; /* Function to Insert Node at the End of the Linked List */ void insert_end(struct node **head, int ele) { /* Creating a Node */ struct node *new_node; new_node = (struct node*)malloc(sizeof(struct node)); new_node->data = ele; new_node->next = NULL; /* Check whether the linked list is empty or not */ /* If Linked List is empty, then new node will become head of the linked list */ if(*head == NULL) { *head = new_node; return; } /* If Linked List is not empty, then traverse the complete linked list and point the pointer of last node of the linked list to the new node of the linked list */ struct node *temp = NULL; temp = (*head); while(temp->next != NULL) temp=temp->next; temp->next = new_node; } /* Function to Sort the Linked List using Bubble Sort */ void bubbleSort(struct node *head) { struct node *temp1; struct node *temp2; for(temp1 = head; temp1!=NULL; temp1=temp1->next) { for(temp2 = temp1->next; temp2!=NULL; temp2=temp2->next) { if(temp1->data > temp2->data) { int temp = temp1->data; temp1->data = temp2->data; temp2->data = temp; } } } } /* Function to Print the Linked List */ void print(struct node *head) { struct node *p = head; while(p!=NULL) { cout<<p->data<<" "; p=p->next; } } int main() { struct node *head; head = NULL; /* Inserting Some Nodes of the Linked List */ insert_end(&head,4); insert_end(&head,3); insert_end(&head,2); insert_end(&head,1); cout<<"The linked list elements before sorting:\n"; print(head); bubbleSort(head); cout<<"\n The linked list elements after sorting:\n"; print(head); }
OUTPUT: The linked list elements before sorting: 4 3 2 1 The linked list elements after sorting: 1 2 3 4
Related Posts:
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes of the Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.
- Delete without head pointer of the Linked List.
- Delete All Occurrences of particular node of the Linked List.
- Delete Alternate Nodes of the Linked List.
- Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
- Remove Duplicate Nodes from an Unsorted Linked List.
- Remove Duplicate Nodes from a Sorted Linked List.
- Find Union and Intersection of Two Linked List.
- Merge Two Sorted Linked List.
- Insert a New Node at the Sorted Linked List.
- Reverse a Linked List.
- Reverse a Linked List Using Stack.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.