Data Structures-Insertion Sort

Insertion Sort

Insertion sort is a sorting algorithm in which we insert each element onto its proper place in a sorted array. This is not as efficient as quicksort, merge sort, and other sorting algorithms.

Technique

Let’s assume an array that is already sorted. In the beginning, A[0] is the only element on the sorted set.
In pass 1, A[1] is placed at its proper index in the array, and in pass 2, A[2] is placed in the proper index. If one needs to insert an element A[x], it needs to be compared with all the elements in the array.

Algorithm

Psuedocode:

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
 
   for i = 1 to length(A) inclusive do:
 
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
 
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
 
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
 
end procedure

Reference

Insertion sort