Insertion Sort Algorithm

Subscribe to my newsletter and never miss my upcoming articles

Today we will talk about Insertion Sort Algorithm.

In insertion sort we traverse the unsorted array sequentially.

It is similar to selection sort because both are in-place sort and both use the first (left) part of the unsorted array as the sorted array and last part (right) as the unsorted array. If the sorted part has n sorted elements, then the next element we process has to traverse and compare with all elements of the sorted part until it reaches its point of insertion.

In insertion we have to take chunks of two all the time.

take the following sample array: A = [40, 20, 30, 10, 60, 15, 0, 1]

step 1: take A[0] = 40 and A[1] = 20, compare both values, if the second element is less than the second value then swap the values.

          The modified array:  A =  [20, 40, 30, 10, 60, 15, 0, 1]

step 2: take A[1] = 40 and A[2] = 30, compare both values, if the second element is less than the second value then swap the values.

          The modified array:  A =  [20, 30, 40, 10, 60, 15, 0, 1]

step 3: take A[2] = 40 and A[3] = 10, compare both values, if the second element is less than the second value then swap the values. In this case we will continue comparing the value of A[3] against all the values in the sorted part until it reaches its insertion point.

          A =  [20, 30, 10, 40, 60, 15, 0, 1]
          A =  [20, 10, 30, 40, 60, 15, 0, 1]
          A =  [10, 20, 30, 40, 60, 15, 0, 1]

          The modified array:  A =  [10, 20, 30, 40, 60, 15, 0, 1]

step 4: take A[3] = 40 and A[4] = 60, compare both values, if the second element is less than the second value then swap the values.

          The modified array:  A =  [10, 20, 30, 40, 60, 15, 0, 1]

step 5: take A[4] = 60 and A[5] = 15, compare both values, if the second element is less than the second value then swap the values. n this case we will continue comparing the value of A[5] against all the values in the sorted part until it reaches its insertion point.

           A =  [10, 20, 30, 40, 15, 60, 0, 1]
           A =  [10, 20, 30, 15, 40, 60, 0, 1]
           A =  [10, 20, 15, 30, 40, 60, 0, 1]
           A =  [10, 15, 20, 30, 40, 60, 0, 1]    - *10 is less than 15 so we found the 
                                                            insertion point we stop traversing 
                                                            the sorted array.*

          The modified array:   A =  [10, 15, 20, 13, 40, 60, 0, 1]

step 6: take A[5] = 60 and A[6] = 0, compare both values, if the second element is less than the second value then swap the values. n this case we will continue comparing the value of A[6] against all the values in the sorted part until it reaches its insertion point.

           A =  [10, 20, 30, 40, 15, 60, 0, 1]
           A =  [10, 20, 30, 15, 40,   0, 60, 1]
           A =  [10, 20, 15, 30,    0, 40,  60, 1]
           A =  [10, 15, 20,  0,  30, 40, 60, 1]  
           A =  [10, 15,  0, 20,  30, 40, 60, 1] 
           A =  [10,  0, 15, 20,  30, 40, 60, 1] 
           A =  [0, 10, 15, 20,  30, 40, 60, 1]   -  we reached the head of the sorted 
                                                             array  that means we found the 
                                                             insertion point we stop traversing 
                                                             the sorted array.*

          The modified array:    A =  [0, 10, 15, 20,  13, 40, 60, 1]

step 7: take A[6] = 60 and A[7] = 1, compare both values, if the second element is less than the second value then swap the values. n this case we will continue comparing the value of A[6] against all the values in the sorted part until it reaches its insertion point.

           A =  [0, 10, 15, 20,  30, 40, 60, 1]
           A =  [0, 10, 15, 20,  30, 40,   1, 60]
           A =  [0, 10, 15, 20,  30,   1,   40, 60]
           A =  [0, 10, 15, 20,  1,   30,   40, 60]
           A =  [0, 10, 15, 1,  20,   30,   40, 60]
           A =  [0, 10, 1, 15,  20,   30,   40, 60]
           A =  [0, 1, 10, 15,  20,   30,   40, 60]  - since 0 is less than 1, then 
                                                                that means we found the 
                                                                insertion point we stop traversing 
                                                                the sorted array. 


          **The fully sorted array:   
          A =  [0, 1, 10, 15,  20,   30,   40, 60]**

Please see live code here:

Thanks for reading this article.

Let's Connect

Next Article: undecided - maybe another sort algorithm

No Comments Yet