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:

1. Detect a Loop in a Linked List.
2. Find the Length of the Loop present in the Linked List.
3. Detect and Remove Loop from a Linked List.
4. Segregate Even and Odd Nodes of the Linked List.
5. Delete Complete Linked List.
6. Delete Nth Node of the Linked List.
7. Delete without head pointer of the Linked List.
8. Delete All Occurrences of particular node of the Linked List.
9. Delete Alternate Nodes of the Linked List.
10. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
11. Remove Duplicate Nodes from an Unsorted Linked List.
12. Remove Duplicate Nodes from a Sorted Linked List.
13. Find Union and Intersection of Two Linked List.
14. Merge Two Sorted Linked List.
15. Insert a New Node at the Sorted Linked List.
16. Reverse a Linked List.
17. Reverse a Linked List Using Stack.
18. Printing Linked List in Reverse Order without actually reversing the Linked List.
19. Swap Adjacent Elements of the Linked List.
20. Count All Occurrences of a Particular Node in a Linked List.

---