Insertion Sort Algorithm on Singly Link List

We will sort a singly link list using the bubble sort technique.

Example:

Input : 20->30->40->10

Output :10->20->30->40

Input : 20->4->3

Output : 3->4->20

Sorting Technique

The insertion sort technique works similarly in the way of playing cards technique.

The whole link list is divided into two parts. One is called sorted, and the other one is called unsorted.

Every time one node is taken from the unsorted link list and placed at its original place in the sorted link list.

C Code:

 #include <stdio.h>
 #include <stdlib.h>
 struct node {
     int val;
     struct node* next;
     struct node* prev;
 };
 void insert_beg(struct node** head, int val)
 {
     struct node* nn = (struct node*)malloc(sizeof(struct node));
     nn->val = val;
     nn->prev = NULL;
     nn->next = *head;
     if (*head == NULL) {
         *head = nn;
         return;
     }
     (*head)->prev = nn;
     *head = nn;
 }
 void insert_last(struct node** head, int val)
 {
     struct node* nn = (struct node*)malloc(sizeof(struct node));
     nn->val = val;
     nn->next = NULL;
     struct node* trav = *head;
     while (trav->next != NULL) {
         trav = trav->next;
     }
     trav->next = nn;
     nn->prev = trav;
 }
 void print(struct node* head)
 {
     struct node* trav = head;
     while (trav->next != NULL) {
         printf("%d->", trav->val);
         trav = trav->next;
     }
     printf("%d\n", trav->val);
 }
 int size(struct node* head)
 {
     struct node* trav = head;
     int c = 0;
     while (trav != NULL) {
         c++;
         trav = trav->next;
     }
     return c;
 }
 void insertion_sort(struct node** head)
 {
     struct node* i = *head;
     struct node* trav = *head;
     struct node* j;
     int n;
     if (*head != NULL && (*head)->next != NULL) {
         while (trav->next != NULL) {
             trav = trav->next;
         }
         for (i = *head; i != trav; i = i->next) {
             n = i->next->val;
             for (j = i; j != *head; j = j->prev) {
                 if (j->val > n) {
                     j->next->val = j->val;
                 }
                 else {
                     j->next->val = n;
                     break;
                 }
             }
             if (j == *head) {
                 if (j->val < n) {
                     j->next->val = n;
                 }
                 else {
                     j->next->val = j->val;
                     (*head)->val = n;
                 }
             }
         }
     }
 }
 int main()
 {
     struct node* head = NULL;
     int arr[4] = { 20, 30, 40, 10 }; // Create the link list
     printf("Before sorting: ");
 // Print list before sort
     for (int i = 0; i < 4; i++) {
         printf("%d->", arr[i]);
     }
     for (int i = 0; i < 4; i++) {
         if (head == NULL) {
             insert_beg(&head, arr[i]);
         }
         else
             insert_last(&head, arr[i]);
     }
     insertion_sort(&head); // sort the link list
     printf("\nAfter Sorting: ");
     print(head);
     return 0;
 }

C++ Code:

 #include <bits/stdc++.h>
 #include <iostream>
 using namespace std;
 struct node {
     int data;
     node* next;
 };
 /*Function that inserts nodes in front of
     Given Linked List*/
 void InsFront(node** head, int data)
 {
     node* temp = new node;
     temp->data = data;
     temp->next = *head;
     *head = temp;
 }
 /*Function that inserts nodes in sorted order*/
 void sorted_insert(node** head, int n)
 {
     node* temp = new node;
     temp->data = n;
     if (*head == NULL || (*head)->data >= n) {
         temp->next = *head;
         *head = temp;
     }
     else {
         node* prev = *head;
         node* curr = prev->next;
         while (curr != NULL) {
             if (prev->data < n && n < curr->data) {
                 prev->next = temp;
                 temp->next = curr;
                 return;
             }
             prev = prev->next;
             curr = curr->next;
         }
         prev->next = temp;
         temp->next = curr;
     }
 }
 /*Function to apply insertion sort on list*/
 void ins_sort(node** head)
 {
     if (*head == NULL)
         return;
     node* sorted_list = NULL;
     node* curr = *head;
     while (curr != NULL) {
         sorted_insert(&sorted_list, curr->data);
         curr = curr->next;
     }
     *head = sorted_list;
 }
 void printList(node* head)
 {
     while (head != NULL) {
         cout << head->data << "-> ";
         head = head->next;
     }
 }
 /* Driver program to test above functions*/
 int main()
 {
     node* head = NULL;
 // Create the link list
     InsFront(&head, 40);
     InsFront(&head, 30);
     InsFront(&head, 10);
     InsFront(&head, 20);
     cout << "Before sorting: "; // print list before sort
     printList(head);
     /*Calling Insertion sort function*/
     ins_sort(&head); // Call insertion sort
     cout << "\nAfter sorting: ";
     printList(head); // print list after sort
     return 0;
 }

Output:

 Before sorting: 20-> 10-> 30-> 40->
 After sorting: 10-> 20-> 30-> 40->

Complexities:

Worst complexity: O( n^2 )

Average complexity: O( n^2 )

Best complexity: O( n )

Space complexity: O(1)

DAA: Insertion Sort Algorithm on Singly Link List