Insert sort on linked list
In last post Insert in sorted order in linked list, how to insert a new node into sorted list so that resultant list is also sorted. We will be using the same concept and implement insert sort on linked list.
First of all, let’s understand what is insertion sort. Insertion sort is a sorting technique in which, each element is take out from input and insert into it’s appropriate place in output. When all elements of inputs are inserted at their right place, list is sorted.
Insert sort on linked list algorithm
Array based implementation requires movement of all elements on to right of correct place by one position. At any given elements, all elements on to left of that are sorted and this current element needs to be inserted into that sorted part of array. And it is done for all n elements, hence complexity of insertion sort is O(n2). Below example explains how insertion sort works:
Input: 3,2,1,6,4,9,7,5 Step 1 : Take out 3. There is no elements on left, move Step 2 : Take out 2. Now since 2 < 3, it should be before 3. Insert it. Array : 2,3,1,6,4,9,7,5 Step 3 : Take out 1, it is smaller than 2 and 3, and should be placed before them. Insert it. Array : 1,2,3,6,4,9,7,5 Step 4 : Take out 6. It is greater than all elements on left. Skip it. Array : 1,2,3,6,4,9,7,5 Step 5 : Take out 4, 4 < 6 and greater than 3, insert 4 between 3 and 6 Array : 1,2,3,4,6,9,7,5 Step 6 : Take out 9, It is greater than all elements on left, skip it. Array : 1,2,3,4,6,9,7,5 Step 7 : Take out 7. It is less than 9 and greater than 6. Insert it in between 6 and 9 Array : 1,2,3,4,6,7,9,5 Step 8 : Take out 5, 5 is less than 6 and greater than 4. Insert it there. Array : 1,2,3,4,5,6,7,9 (output)
1. Start i = 0 to n 2. Let's say x = array[i] 3. Start from j = i and j > =0 3.a if x < array[j] array[j+1] = a[j] and move left i.e j-- 3.b if x > array[j] array[j] =
C implementation of insert sort on arrays
Implementing insert sort on linked list is simple as we don’t have to move any node right. Just take out the node and insert it at appropriate place in already sorted list, this where will use : Insert in sorted order in linked list
Insert sort on linked list implementation
In implementation, we initialize a new list which is NULL to start with, then insert nodes of original list into result list in sorted order. Note that we are not allocating any new memory, only nodes are moved from one place to another.
Output of insert sort
Original list : 2->7->6->12->10->1->NULL Output : 1->2->6->7->10->12->NULL
Complexity of insert sort on linked list is also O(n2).
Please share your suggestions, or if something is wrong. We would love to hear what you have to say. Sharing is caring. If you want to contribute to website or have an interview experience to share, please contact us.