C program of Bubble sort using linked list

Mr Coder August 23, 2012 7

C program of bubble sort using linked list : In my previous code of Bubble sort algorithm, we have seen how to write a C program of bubble sort using for loop. Today we will learn how to write c code of bubble sort using linked list.

Bubble sort algorithm is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Let us see how to implement bubble sort algorithm using linked list in C programming. In my below code i have taken number of elements and elements to be sorted as input from the user and then displayed the sorted list of elements obtained by Bubble sort using Linked list.

C program of bubble sort using linked list :

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct lnode {
 int data;
 struct lnode *next;
} *head, *visit;

/* add a new entry to the linked list */
void llist_add(struct lnode **q, int num);
/* preform a bubble sort on the linked list */
void llist_bubble_sort(void);
/* print the entire linked list */
void llist_print(void);

int main(void) {
 /* linked list */
 struct lnode *newnode = NULL;
 int i = 0,num,a[20]; /* a general counter */
 printf("----------------------------------------------------------------------\n");
 printf("-------------------made by C code champ ------------------------------\n");
 printf("----------------------------------------------------------------------\n");
 printf("\n\n\t BUBBLE SORT ALGORITHM USING LINKED LIST\n");    
 printf("\nEnter the number of elements : ");
 scanf("%d",&num);
 /* load some random values into the linked list */
 printf("\nEnter the elements to be sorted : \n");
 for(i = 0; i < num; i++) {
  scanf("%d",&a[i]);
  llist_add(&newnode, a[i]);
 }

 head = newnode;
 printf("\nList of input elements :\n");
 llist_print();
 printf("\n\nSorted List of elements by bubble sort :\n");
 llist_bubble_sort();
 llist_print();
 getch();
 return 0;
}

/* adds a node at the end of a linked list */
void llist_add(struct lnode **q, int num) {
 struct lnode *tmp; 

 tmp = *q;

 /* if the list is empty, create first node */
 if(*q == NULL) {
  *q = malloc(sizeof(struct lnode));
   tmp = *q;
 } else {
  /* go to last node */
  while(tmp->next != NULL)
   tmp = tmp->next;

   /* add node at the end */
   tmp->next = malloc(sizeof(struct lnode));
   tmp = tmp->next;
 }

 /* assign data to the last node */
 tmp->data = num;
 tmp->next = NULL;
}

/* print the entire linked list */
void llist_print(void) {
 visit = head;

 while(visit != NULL) {
  printf("%d\t", visit->data);
  visit = visit->next;
 }
 printf("\n");
}

/* preform a bubble sort on the linked list */
void llist_bubble_sort(void) {
 struct lnode *a = NULL;
 struct lnode *b = NULL; 
 struct lnode *c = NULL;
 struct lnode *e = NULL; 
 struct lnode *tmp = NULL; 

 /* 
 // the `c' node precedes the `a' and `e' node 
 // pointing up the node to which the comparisons
 // are being made. 
 */
 while(e != head->next) {
 c = a = head;
 b = a->next;
  while(a != e) {
   if(a->data > b->data) {
    if(a == head) {
     tmp = b -> next;
     b->next = a;
     a->next = tmp;
     head = b;
     c = b;
    } else {
     tmp = b->next;
     b->next = a;
     a->next = tmp;
     c->next = b;
     c = b;
    }
   } else {
    c = a;
    a = a->next;
   }
   b = a->next;
   if(b == e)
    e = a;
  }
 }
}

We hope that you all have enjoyed the above C program of Bubble sort using linked list. If you have any issues with the C code or logic used in the program, feel free to contact us in form of comments.

7 Comments »

  1. Jessica April 9, 2013 at 4:48 am - Reply

    why is this not working for a list of names?

  2. storage container June 30, 2013 at 10:41 pm - Reply

    Great article! We are linking to this particularly great
    article on our site. Keep up the great writing.

  3. Steam Wallet Hack 2013 v7.0 July 25, 2013 at 9:53 pm - Reply

    I pay a quick visit day-to-day some websites and sites to read posts, except this web site
    gives feature based writing.

  4. vaping July 28, 2013 at 12:19 am - Reply

    My brother suggested I might like this blog. He was entirely right.
    This post actually made my day. You can not imagine simply how much time I had spent
    for this information! Thanks!

  5. best Diving Company August 2, 2013 at 9:45 am - Reply

    Have you ever considered about including a little bit more than just your articles?

    I mean, what you say is fundamental and all. Nevertheless imagine if you added
    some great graphics or video clips to give your posts more, “pop”!
    Your content is excellent but with pics and videos, this website could definitely be one of the very best in its niche.
    Superb blog!

  6. yogesh August 7, 2013 at 10:23 pm - Reply

    This code is very helpfull and intelectual.I would have never been thought so deeply to crack the bubble sort for linked list.

  7. piala dunia ku September 8, 2013 at 10:11 am - Reply

    Excellent website you have here but I was wanting
    to know if you knew of any forums that cover the same topics discussed in this
    article? I’d really love to be a part of community where I
    can get advice from other knowledgeable people that share the same interest.
    If you have any recommendations, please let me know. Cheers!

Leave A Response »