Last Updated on April 20, 2023 by Prepbytes
Insertion sort is a simple and efficient sorting algorithm that works well on small or nearly sorted data sets and it works similarly to the way you sort playing cards in your hands. The elements are virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part. Insertion sort is also an ideal sorting algorithm for sorting the singly linked list. Let us study in detail the insertion sort in linked list and understand how the insertion sort using linked list works.
Insertion Sort in Linked List
To perform the insertion sort using linked list, we will be given a singly linked list. We need to return the pointer to the head node after sorting the given linked list.
Input linked list:
Output after performing the insertion sort in linked list:
Explanation: The given linked list is sorted and the sorted linked list is printed in the output.
This problem is not a tricky one. Let’s start performing insertion sort in linked list.
- We just have to extract the elements from the list one by one, insert them in the new list in a sorted way, and return the new list.
- To see how to insert an element in a sorted way in a sorted linked list, check out this – Given a linked list which is sorted, how to insert in a sorted way.
Let us take a brief look at the approach to perform the insertion sort using linked list.
How to Perform Insertion Sort In Linked List?
The approach for performing insertion sort in linked list is going to be pretty simple.
- We will create an empty result singly linked list, which will be sorted.
- Then, we will traverse the given linked list, and for every node that we visit, we will insert the current node in a sorted way in our result list.
- To insert in a sorted way, follow these steps:
- We will traverse our result list and keep comparing every node with our current node.
- As soon as we find a node whose value is greater than the current node, we will insert the current node just before that node.
- If the current node value is greater than every other node of our result list, then we will append the current node at the end.
- After complete traversal, change the head of the given linked list to the head of the result list.
- Finally, return the head of the sorted linked list.
Let’s move to the algorithm to perform insertion sort using linked list to understand the approach in a more clear way
Algorithm For Performing Insertion Sort Using Linked List
Here is the stepwise algorithm for performing the insertion sort in linked list.
- Step 1: Initialize the newly created sorted list as NULL.
- Step 2: Traverse the given singly linked list using a pointer say current.
- For every node, while traversal, store the next of node in a temp variable and remove all of its links.
- Insert the current node in a sorted way in the result list.
- Update the current value with a temp for further traversal.
- Step 3: Once the traversal is over, update the head pointer by making it point to our result list.
- Step 4: Return the head pointer.
Dry Run For Performing Insertion Sort in Linked List
The dry run for the above-mentioned algorithm is given below.
Code Implementation For Performing Insertion Sort in Linked List
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
struct node* head = NULL;
struct node* sorted = NULL;
void push(int val)
{
/* allocate node */
struct node* newnode
= (struct node*)malloc(sizeof(struct node));
newnode->data = val;
/* link the old list off the new node */
newnode->next = head;
/* move the head to point to the new node */
head = newnode;
}
void sortedInsert(struct node* newnode)
{
/* Special case for the head end */
if (sorted == NULL || sorted->data >= newnode->data) {
newnode->next = sorted;
sorted = newnode;
}
else {
struct node* current = sorted;
/* Locate the node before the point of insertion
*/
while (current->next != NULL
&& current->next->data < newnode->data) {
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
}
// function to sort a singly linked list
// using insertion sort
void insertionsort()
{
struct node* current = head;
// Traverse the given linked list and insert every
// node to sorted
while (current != NULL) {
// Store next for next iteration
struct node* next = current->next;
// insert current in sorted linked list
sortedInsert(current);
// Update current
current = next;
}
// Update head to point to sorted linked list
head = sorted;
}
/* Function to print linked list */
void printlist(struct node* head)
{
while (head != NULL) {
printf("%d->", head->data);
head = head->next;
}
printf("NULL");
}
// Driver program to test above functions
int main()
{
push(5);
push(20);
push(4);
push(3);
push(30);
printf("Linked List before sorting:\n");
printlist(head);
printf("\n");
insertionsort(head);
printf("Linked List after sorting:\n");
printlist(head);
}
#include <bits stdc++.h="">
using namespace std;
struct Node {
int val;
struct Node* next;
Node(int x)
{
val = x;
next = NULL;
}
};
class LinkedlistIS {
public:
Node* head;
Node* newhead;
void push(int val)
{
Node* newnode = new Node(val);
newnode->next = head;
head = newnode;
}
void insertionSort(Node* headref)
{
newhead = NULL;
Node* current = headref;
while (current != NULL) {
Node* temp = current->next;
sortedInsert(current);
// Update current
current = temp;
}
head = newhead;
}
void sortedInsert(Node* newnode)
{
if (newhead == NULL || newhead->val >= newnode->val) {
newnode->next = newhead;
newhead = newnode;
}
else {
Node* current = newhead;
while (current->next != NULL
&& current->next->val < newnode->val) {
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
}
void printlist(Node* head)
{
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
}
};
int main()
{
LinkedlistIS list;
list.head = NULL;
list.push(3);
list.push(1);
list.push(2);
list.push(4);
list.push(5);
cout << "Linked List before sorting" << endl;
list.printlist(list.head);
cout << endl;
list.insertionSort(list.head);
cout << "Sorted Linked List" << endl;
list.printlist(list.head);
}
public class LinkedlistIS
{
node head;
node newhead;
class node
{
int val;
node next;
public node(int val)
{
this.val = val;
}
}
void push(int val)
{
node newnode = new node(val);
newnode.next = head;
head = newnode;
}
void insertionSort(node headref)
{
newhead = null;
node current = headref;
while (current != null)
{
node temp = current.next;
sortedInsert(current);
current = temp;
}
head = newhead;
}
void sortedInsert(node newnode)
{
if (newhead == null || newhead.val >= newnode.val)
{
newnode.next = newhead;
newhead = newnode;
}
else
{
node current = newhead;
while (current.next != null && current.next.val < newnode.val)
{
current = current.next;
}
newnode.next = current.next;
current.next = newnode;
}
}
void printlist(node head)
{
while (head != null)
{
System.out.print(head.val + " ");
head = head.next;
}
}
public static void main(String[] args)
{
LinkedlistIS list = new LinkedlistIS();
list.push(3);
list.push(1);
list.push(2);
list.push(4);
list.push(5);
System.out.println("Linked List before Sorting..");
list.printlist(list.head);
list.insertionSort(list.head);
System.out.println("\nSorted Linked List");
list.printlist(list.head);
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insertionSort(head_ref):
sorted = None
current = head_ref
while (current != None):
next = current.next
sorted = sortedInsert(sorted, current)
current = next
head_ref = sorted
return head_ref
def sortedInsert(head_ref, new_node):
current = None
if (head_ref == None or (head_ref).data >= new_node.data):
new_node.next = head_ref
head_ref = new_node
else:
current = head_ref
while (current.next != None and
current.next.data < new_node.data):
current = current.next
new_node.next = current.next
current.next = new_node
return head_ref
def printList(head):
temp = head
while(temp != None):
print( temp.data, end = " ")
temp = temp.next
def push( head_ref, new_data):
new_node = Node(0)
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref
a = None
a = push(a, 3)
a = push(a, 1)
a = push(a, 2)
a = push(a, 4)
a = push(a, 5)
print("Linked List before sorting ")
printList(a)
a = insertionSort(a)
print("\nLinked List after sorting ")
printList(a)
Output
Linked List before Sorting.
5 4 2 1 3
Sorted Linked List
1 2 3 4 5Time Complexity For Performing Insertion Sort using Linked List: O(n2), as we are using nested traversal
Space Complexity For Performing Insertion Sort using Linked List: O(1), as no extra is required depending on the size of the input.
Frequently Asked Questions(FAQs)
Here are some Frequently Asked Questions related to insertion sort in linked list.
Ques 1. What is insertion sort?
Ans. Insertion sort is a simple sorting algorithm that works by dividing the input into two sections: a sorted section and an unsorted section. Initially, the sorted section is empty, and the unsorted section contains all the elements in the input. The algorithm then iterates through the unsorted section, comparing each element with the elements in the sorted section and inserting it in the correct position.
Ques 2. Why insertion is faster in the LinkedList in comparison to ArrayList?
Ans. A LinkedList consumes a bit more memory than an ArrayList since every node stores two references to the previous and next elements. The insertion, addition, and removal operations are faster in a LinkedList because there is no resizing of an array done in the background.
Ques 3. What happens if the linked list is empty during insertion sort?
Ans. If the linked list is empty during insertion sort, the algorithm simply returns the empty list.
Ques 4. Is insertion sort in linked list stable?
Ans. Yes, insertion sort in linked list is stable, meaning that the order of equal elements in the original list will be preserved after sorting.