Insertion Sort Using Linked List

Write a Program to implement c Insertion Sort Using Linked List. This tutorial is intended to provide you information about what insertion sort algorithm is and how to implement it in programming rather than it’s technical stuff, properties and comparision with other sorting algorithm.

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted.

For example : The lower part of an list is maintained to be sorted. An element which is to be ‘inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n²), where n is the number of items.

Below is simple insertion sort algorithm for linked list.

1) Create an empty sorted (or result) list

2) Traverse the given list, do following for every node.

……a) Insert current node in sorted way in sorted or result list.

3) Change head of given linked list to head of sorted (or result) list.

Below is the source code for C Program to implement Insertion Sort Using Linked List which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

/*  C Program to implement Insertion Sort Using Linked List  */

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

struct lnode {
 char *str;
 struct lnode *next;
};

struct lnode *insert(char *data, struct lnode *list);
void free_list(struct lnode *list);
void print_list(struct lnode *list);



int main()
{
     char line[1024];
     struct lnode *list;

     list = NULL;
     while((fgets(line, 1024, stdin)) != NULL)
      list = insert(line, list);
     print_list(list);
     free_list(list);
     return 0;
}



struct lnode *insert(char *data, struct lnode *list) {
 struct lnode *p;
 struct lnode *q;

 /* create a new node */
 p = (struct lnode *)malloc(sizeof(struct lnode));
 /* save data into new node */
 p->str = strdup(data);

 /* first, we handle the case where `data' should be the first element */
 if(list == NULL || strcmp(list->str, data) > 0) {
  /* apperently this !IS! the first element */
  /* now data should [be|becomes] the first element */
  p->next = list;
  return p;
 } else {
  /* search the linked list for the right location */
  q = list;
  while(q->next != NULL && strcmp(q->next->str, data) < 0) {
   q = q->next;
  }
  p->next = q->next;
  q->next = p;
  return list;
 }
}

void free_list(struct lnode *list) {
 struct lnode *p;

 while(list != NULL) {
  p = list->next;
  free(list);
  list = p;
 }
}

void print_list(struct lnode *list) {
 struct lnode *p;

 for(p = list; p != NULL; p = p->next)
  printf("%s", p->str);
}

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

Thanks for reading the post….

3 3 votes

Article Rating