C program for performing Bubble sort on Linked List

Last Updated on July 27, 2023 by Mayank Dham

A linked list has been provided, and bubble sort must be used to order it. When using the bubble sorting method, neighboring components that are in the wrong order are continuously switched. The bubble sort linked list in C will be explained in more detail below as we are required to write a program that sorts the elements of linked list using bubble sort technique.

How to Perform the Bubble Sort Linked List in C?

We will be provided a singly linked list to work with in this task. The provided list must be sorted using bubble sort in C. Instead of using values, the bubble sort will be applied to nodes. Instead of swapping values, we must switch the nodes.

Let’s try to understand the problem statement with the help of examples.

Suppose the given list is:

• According to the problem statement, we have to sort the given list using bubble sort. What do we usually do? We usually swap the node data. But here, we have to swap the nodes and not their data.

• In the first step, suppose we have to swap 5 and 1. So, we will swap the nodes and not their data. So, the linked list after first step will be 1 → 5 → 4 → 2 → 8. In this way, swapping will happen and our final sorted linked list will be:

If the given linked list is 6 → 3 → 1 → 9 → 12 → 15 → 5.

• Then after applying bubble sort on the linked list, the sorted list will be 1 → 3 → 5 → 6 → 9 → 12 → 15.

This is not a difficult question. We only need to do a standard bubble sort on the list. The sole variation is that we’ll exchange the nodes themselves rather than just the data of nearby nodes.

Let us have a glance at the approach by referring online coding classes.

Approach and Algorithm for performing bubble sort using linked list in C

We will be discussing how we can perform bubble sort linked list in C using different methods.

Using Swap() function

• In the swap() function, we will swap two adjacent nodes.
• Let the two adjacent nodes be p1 and p2. Now we will create 2 pointer ptr1 and ptr2, and will make ptr1 point to p1 and ptr2 point to p2.
• Now, we will create a pointer temp, and will make it point to the next of ptr2.
• We will make next of ptr2 point to ptr1 and next of ptr1 point to temp.
• In this way, following the above steps, the two adjacent nodes p1 and p2 will get swapped.

Dry Run of Swap() function

Using BubbleSort() function

• In this method, we will perform Bubble Sort on the Nodes.
• First, we need the count of the number of nodes in the list. The count can be found with a single list traversal.
• Now, the first loop is going to run from 0 to count – 1.
• Inside the first loop, we will create a node pointer h that will point to the head and a variable swapped, which we will initialize with 0.
• The nested loop will run from 0 to count – i – 1.
• Inside the nested loop, we will check if the adjacent nodes are following ascending order or not.
  • If not, we will swap the nodes and the value of swapped will become 1.
• After the if condition, we will increment the h.
• Now, after the inner loop, if the value of the swapped remains 0, it means that the list is sorted, and we will break the loop. Otherwise, we will continue the loop.

**Dry Run – BubbleSort()**

### Code Implementation

#include <stdio.h>
#include <stdlib.h>
  
 
struct Node {
    int data;
    struct Node* next;
} Node;
  
 
struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
    struct Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}
  
 
int bubbleSort(struct Node** head, int count)
{
    struct Node** h;
    int i, j, swapped;
  
    for (i = 0; i <= count; i++) {
  
        h = head;
        swapped = 0;
  
        for (j = 0; j < count - i - 1; j++) {
  
            struct Node* p1 = *h;
            struct Node* p2 = p1->next;
  
            if (p1->data > p2->data) {
                *h = swap(p1, p2);
                swapped = 1;
            }
  
            h = &(*h)->next;
        }
  
        
        if (swapped == 0)
            break;
    }
}
 
 
void printList(struct Node* n)
{
     while (n->next != NULL) {
        printf("%d -> ", n->data);
        n = n->next;
    }
    printf("%d ", n->data);
    printf("\n");
}
  
 
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;
}
  
int main()
{
    int arr[] = { 5, 1, 4, 2, 8 };
    int list_size, i;
    struct Node* start = NULL;
    list_size = sizeof(arr) / sizeof(arr[0]);
    
    for (i = 0; i < list_size; i++){
        insertAtTheBegin(&start, arr[i]);
    }

    printf("Linked list before sorting\n");
    printList(start);

    bubbleSort(&start, list_size);
    printf("Linked list after sorting\n");
    printList(start);
    return 0;
}

**Output**

Linked list before sorting
8 -> 2 -> 4 -> 1 -> 5
Linked list after sorting
1 -> 2 -> 4 -> 5 -> 8

**Time Complexity:** O(n2), where n is the total number of nodes in the Singly Linked List.

**Conclusion**
Performing bubble sort on a linked list involves swapping adjacent elements until the entire list is sorted. The algorithm compares and swaps elements pairwise, moving the larger elements toward the end of the list in each iteration. By repeatedly applying this process, the linked list gradually becomes sorted in ascending order. Bubble sort is a simple and intuitive sorting algorithm, but it may not be the most efficient for large lists.

## Frequently Asked Questions (FAQs)
**Q1: How does bubble sort work on a linked list?**
**Ans.** Bubble sort on a linked list works by repeatedly comparing and swapping adjacent elements until the entire list is sorted. The algorithm traverses the linked list, comparing each node with its adjacent node. If the nodes are in the wrong order, their positions are swapped. This process is repeated until the list is sorted.

**Q2: What is the time complexity of bubble sort on a linked list?**
**Ans.** The time complexity of bubble sort on a linked list is O(n^2), where n is the number of nodes in the list. This is because the algorithm requires nested iterations to traverse and compare each element in the list. As a result, bubble sort is not considered efficient for large lists.

**Q3: Can bubble sort be used for sorting a doubly linked list?**
**Ans.** Yes, bubble sort can be used for sorting a doubly linked list as well. The process is similar to sorting a singly linked list. However, since a doubly linked list has backward pointers, the swapping process involves adjusting the pointers of adjacent nodes accordingly.

**Q4: Are there more efficient sorting algorithms for a linked list?**
**Ans.** Yes, there are more efficient sorting algorithms for a linked list, such as merge sort and insertion sort. These algorithms have better time complexities compared to bubble sort and are often preferred for larger lists. Merge sort, in particular, is widely used for sorting linked lists efficiently.

Other C Programs
C program to calculate percentage of 5 subjects
C program to convert binary number to decimal number
C program to convert celsius to fahrenheit
C program to convert infix to postfix
C program to find area of circle
C program to find roots of quadratic equation
C program to reverse a number
C program for merge sort for linked lists
C program to add two numbers
C program to reverse a linked list