INSERTION SORT
As part of my Design & Analysis of Algorithms Course, I’ve decided to write on Insertion Sort Algorithm.
WHAT IS INSERTION SORT?
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
INSERTION SORTING STEPS:
~ First element is always sorted.
~ Pick the next element.
~Compare with all the elements in sorted section.
~Shift all the the elements in sorted section that is greater than the value to
sorted.
~ Insert the value.
~ Repeat until the array is sorted.
INSERTION SORT EXAMPLE:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
IMPORTANT CHARACTERISTICS OF INSERTION SORT
~ It is efficient for smaller data sets, but very inefficient for larger lists.
~ Insertion Sort is adaptive, that means it reduces its total number of steps if
given a partially sorted list, hence it increases its efficiency.
~ Its space complexity is less. Insertion sort requires a single additional memory space.
Time Complexity
O(n*2)
Auxiliary Space
O(1)
Boundary Cases
Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
Algorithmic Paradigm
Incremental Approach
How to implement Insertion Sort for Linked List?
~ Create an empty sorted (or result) list.
~ Traverse the given list, do following for every node.
……a) Insert current node in sorted way in sorted or result list.
~ Change head of given linked list to head of sorted (or result) list.