Sort a linked list using insertion sort.

Sort a linked list using insertion sort.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

 

Insertion sort is a comparison based sorting algorithm.
In this algorithm we divide the list into 2 parts. The left most part is sorted part, and the right most part is unsorted part.

In insertion sort, after each pass at least 1 of the element will be in the correct sorted position.

Analogy:

You can think insertion sort as a card playing game. Here we pick a card and place it in the correct position.
If you have only 1 card, it will be moved to the first position. After that we pick another card and place it in the correct position. We repeat these steps until we sort all the cards.

One thing to remember is, one we pick the new card, we check the sorted part to see where the new card fits.

Let us analyze by taking an example:

We try to sort the given elements “7 2 4 1 5 3”
We use “|” to indicate sorted and unsorted part.

Pass 1:
7 | 2 4 1 5 3

Pass 2:
2 7 | 4 1 5 3

Pass 3:
2 4 7 | 1 5 3

Pass 4:
1 2 4 7 | 5 3

Pass 5:
1 2 4 5 7 | 3

Pass 6:
1 2 3 4 5 7

Solution explanation:

In the solution, we take 3 reference pointers.
helper_node
curr_node

We take original head pointer as partially sorted list, then start from second node.
Each time we select a node, we check if the value is less than the head. If it is, then we check and insert it in correct position.
Since there is a possibility that there can be elements whose value is lesser than head value, and has to be inserted before head. Hence we have created “helper_node”. This will act as new head once sorting is completed.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
	int data;
	Node *next;

	Node(int x)
	{
		data = x;
		next = NULL;
	}
};


void print_list(Node *head)
{
	Node *start = head;

	while(start)
	{
		cout<<start->data<<" -> ";
		start = start->next;
	}
	cout<<"\n";
}

Node * sort_list_using_insertion_sort(Node *head)
{
//helper_node
	Node* helper_node = new Node(-1);
	Node* curr_node = helper_node;
//head node is the partially sorted list
	while (head) 
	{
		Node *next = head->next;
		curr_node = helper_node;

		while (curr_node->next && curr_node->next->data <= head->data) 
		{
			curr_node = curr_node->next;
		}
//insert the node in correct position
		head->next = curr_node->next;
		curr_node->next = head;

//move to next node
		head = next;
	}
	return helper_node->next;
}


int main()
{
	Node *head = new Node(2);
	head -> next = new Node(1);
	head -> next -> next = new Node(4);
	head -> next -> next -> next = new Node(3);
	head -> next -> next -> next  -> next = new Node(6);
	head -> next -> next -> next  -> next -> next = new Node(5);
	head -> next -> next -> next  -> next -> next -> next = new Node(8);

	cout<<"The original list = "<<endl;
	print_list(head);

	cout<<"Sorting the list ... "<<endl;;
	Node *new_head = sort_list_using_insertion_sort(head);

	cout<<"\nAfter sorting: "<<endl;

	print_list(new_head);


	return 0;
}

Output:

The original list =
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 ->
Sorting the list …

After sorting:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 ->