In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time.
Here is the strategy for linked list insertion sort. We maintain two lists; one sorted and another unsorted. Initially the sorted list is empty and the unsorted list will be the original list. In each iteration, we remove a node from the unsorted list and add it the sorted list in proper position. I re-used the procedure for inserting data into a sorted linked list from this post.
The following diagram should give you some understanding of the procedure.
Here is the C++ implementation of the above algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| struct ListNode { | |
| int val; | |
| ListNode *next; | |
| ListNode(int x) : val(x), next(NULL) {} | |
| }; | |
| ListNode * Add(ListNode *head, int d) | |
| { | |
| ListNode *temp = new ListNode(d); | |
| temp->next = head; | |
| return temp; | |
| } | |
| void Print(ListNode *head) | |
| { | |
| while( head ) | |
| { | |
| cout << head->val << " "; | |
| head = head->next; | |
| } | |
| cout << endl; | |
| } | |
| ListNode * SortedInsert(ListNode * head, ListNode *newNode ) | |
| { | |
| //special case: newnode to be added as first node | |
| if( head == NULL || head->val >= newNode->val) | |
| { | |
| newNode->next = head; | |
| head = newNode; | |
| return head; | |
| } | |
| ListNode *ptr = head; | |
| ListNode *prev = NULL; | |
| while ( ptr != NULL && ptr->val < newNode->val ) | |
| { | |
| prev = ptr; | |
| ptr = ptr->next; | |
| } | |
| newNode->next = ptr; | |
| prev->next = newNode; | |
| return head; | |
| } | |
| ListNode* InsertionSort(ListNode *head) | |
| { | |
| if( !head || !head->next ) | |
| return head; | |
| ListNode * ptr = head->next; | |
| ListNode * result = head; | |
| result->next = NULL; | |
| while ( ptr ) | |
| { | |
| ListNode *temp = ptr; | |
| ptr = ptr->next; | |
| result = SortedInsert(result,temp); | |
| } | |
| return result; | |
| } | |
| int main() | |
| { | |
| ListNode *head = new ListNode(9); | |
| head = Add(head,3); | |
| head = Add(head,5); | |
| head = Add(head,1); | |
| head = Add(head,6); | |
| head = Add(head,4); | |
| head = Add(head,2); | |
| head = InsertionSort(head); | |
| Print(head); | |
| return 0; | |
| } |
by