C program for performing Bubble sort on Linked List

This blog describes the best approach to implement bubble sort using linked list in c. we have given a linked list and we have to sort it using bubble sort. Bubble sort is a sorting technique that works by repeatedly swapping the adjacent elements if they are in the wrong order. Let’s understand the bubble sort using linked list in c more clearly below.

Problem Statement for performing bubble sort using linked list in C

In this problem, we will be given a singly linked list. We have to sort the given list using bubble sort in C. The bubble sort will be applied on nodes instead of values. We have to swap the nodes instead of the values.

Problem Statement Understanding for performing bubble sort using linked list in C

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 question is not a very complex one. We just have to apply a normal bubble sort on the list. The only difference is that instead of swapping the data of adjacent nodes, we will swap the 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

Swap()

  • 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 – Swap()

BubbleSort()

  • 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

In the above article, we have tried to explain the bubble sort program in C. Therefore, we will conclude bubble sort using linked list in C. Hopefully, You have a clear understanding of this topic now. We hope this article helps you with a hands-on linked list. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQs related to bubble sort using linked list in C

  1. What is a linked list in C?

  2. A linked list is a linear data structure, in which elements are not stored in contiguous memory, linked lists consist of nodes where each node contains two parts one is the data, and the other is the pointer to the next node.

  3. What is a bubble sort in C?

  4. Bubble sort is a sorting algorithm that works by swapping the adjacent elements if they are not in the sorted manner.

  5. How do you sort a linked list using bubble sort?

  6. You can sort a linked list by
    Apply the bubble sort.
    Check two adjacent nodes’ data and compare them.
    Print the list.

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

Leave a Reply

Your email address will not be published. Required fields are marked *