Insertion Sort

This is a sorting algorithm that uses in-place comparisons. A sub-list is kept here that is always sorted. For instance, the lower part of an array is kept in order to be sorted. An element that is to be ‘inserted’ into this sorted sub-list must first identify its right spot and then be inserted there. As a result, the term “insertion sort” was coined.

Unsorted items are moved and added to the sorted sub-list as the array is scanned progressively (in the same array). Because its average and worst-case complexity are Ο(n2), where n is the number of items, this approach is not suitable for huge data sets.

Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocode

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
0

8 thoughts on “Insertion Sort”

  1. Your writing is perfect and complete. baccaratsite However, I think it will be more wonderful if your post includes additional topics that I am thinking of. I have a lot of posts on my site similar to your topic. Would you like to visit once?

    0
  2. I got this website from my friend who informed me concerning this web site and now this time I am browsing
    this site and reading very informative articles
    at this place.

    0

Leave a Comment

Your email address will not be published. Required fields are marked *

16 − 16 =