INSERTION SORT

Insertion sort iterates through the input list, consuming one element each time, and producing a sorted output list. Insertion sort takes one element from the input data at a time, finds where it belongs in the sorted list, and inserts it there. It keeps going until there are no more input elements.

Iterating up the array, increasing the sorted list behind it, is how most sorting is done in-place. It compares the value in each array position to the highest value in the sorted list (which happens to be next to it, in the previous array-position checked). If the element is bigger, it remains in place and goes on to the next. If the value is smaller, it locates the correct spot in the sorted list, moves all the bigger values up to make room, and inserts them into that spot.

Brief Working

In each iteration, it compares the current element with the values in the sorted array. If the current element is greater than the element in the array, then it leaves the element and iterates to the next array element. Otherwise, if the current element is smaller than the array element then it moves the rest of the element in the array by one position and makes space for the current in the sorted array.

This is how Insertion sort takes one input element at a time, iterates through the sorted sub-array, and with each iteration, it inserts one element at its correct position. This is why the algorithm is known as Insertion sort.

Advantages of Insertion Sort:

1. Efficient for small sets of data
2. 2. Simple to implement
3. 3. Passes through the array only once.
4. 4. They are adaptive; efficient for data sets that are already sorted.

Disadvantages of Insertion Sort

1. Less efficient on larger list and arrays

2. Best case: the array is already sorted

3. Worst case: elements are completely backward

Implementation

void insertion_sort ( int A[ ] , int n) 
{
     for( int i = 0 ;i < n ; i++ ) {
    /*storing current element whose left side is checked for its 
             correct position .*/
      int temp = A[ i ];    
      int j = i;
       /* check whether the adjacent element in left side is greater or
            less than the current element. */
          while(  j > 0  && temp < A[ j -1]) {
           // moving the left side element to one position forward.
                A[ j ] = A[ j-1];   
                j= j - 1;
           }
         // moving current element to its  correct position.
           A[ j ] = temp;       
     }  
}

Insertion Sort Time Complexity

• In the worst-case scenario, n will pick all elements and then n shifts to set it to the right position
• In the best-case scenario, that is a sorted array, we will just pick the elements, but no shifting will take place leading it to n time complexity, that is, every element is traversed at least once
• Best Time Complexity: O(n)
• Average Time Complexity: O(n²)
• Worst Time Complexity: O(n²)

Insertion Sort Space Complexity

• No auxiliary space is required in insertion sort implementation. That is, we are not using any arrays, linked list, stack, queue, etc, to store our elements
• Hence space complexity is: O(1)

Algorithm for Insertion Sort

• Step 1 − If the element is the first one, it is already sorted.
• Step 2 — Move to the next element
• Step 3 − Compare the current element with all elements in the sorted array
• Step 4 — If the element in the sorted array is smaller than the current element, iterate to the next element. Otherwise, shift all the greater element in the array by one position towards the right
• Step 5 − Insert the value at the correct position
• Step 6 − Repeat until the complete list is sorted

Examples:

Let’s understand how insertion sort is working in the above image.

• 122, 17, 93, 3, 36

for i = 1(2nd element) to 36 (last element)

i = 1. Since 17 is smaller than 122, move 122 and insert 17 before 122

• 17, 122, 93, 3, 36

i = 2. Since 93 is smaller than 122, move 122 and insert 93 before 122

• 17, 93,122, 3, 36

i = 3. 3 will move to the beginning and all other elements from 17 to 122 will move one position ahead of their current position.

• 3, 17, 93, 122, 36

i = 4. 36 will move to the position after 17, and elements from 93 to 122 will move one position ahead of their current position.

• 3, 17, 36, 93 ,122

Now that we have understood how Insertion Sort works, let us quickly look at a C code to implement insertion sort.

Comparison between Insertion and Selection Sort

The selection sort always requires exactly (n² + n)/2 comparisons to sort n items. In the worst case, an insertion sort requires (n²- n)/2. So, given any non-empty list, insertion sort will always perform fewer comparisons than selection sort.

Conclusion:

That’s all about Insertion sort. It’s one of the fundamental algorithms and as a Java developer, you should know how to write code to sort an integer array using insertion sort. This is quite often asked in Java interviews and written tests. If you want to learn more about Insertion sort and another comparison-based sorting algorithm, then you can read Introduction to Algorithms by Thomas H. Cormen. It has helped me to learn to understand algorithms as well as calculating the time complexity of them.

Read more: https://javarevisited.blogspot.com/2014/12/insertion-sort-algorithm-in-java-to-array-example.html#ixzz6q0gssMGR