/    /  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

  1. Let’s assume an array that is already sorted. In the beginning, A[0] is the only element on the sorted set. 
  2. 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