C Program to implement Insertion Sort Using Linked List

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 Ο(n2), 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);
}