Insertion Sort Algorithm

Overview : Insertion Sort Algorithm

  • Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).

What is Insertion sort

  • In insertion sort algorithm, every iteration moves an element from unsorted portion to sorted portion until all the elements are sorted in the list.
  • Insertion Sort Algorithm sorts array by shifting elements one by one and inserting the right element.
  • It is better than Selection Sort and Bubble Sort algorithms

Steps to Insertion Sort Algorithm

Step 1: Assume that first element in the list is in sorted portion of the list and remaining all elements are in unsorted portion.
Step 2: Consider first element from the unsorted list and insert that element into the sorted list in order specified.
Step 3: Repeat the above process until all the elements from the unsorted list are moved into the sorted list.

insertion algorithm
insertion algorithm

 

Complexity of the Insertion Sort Algorithm

To sort a unsorted list with ‘n’ number of elements we need to make (1+2+3+……+n-1) = (n (n-1))/2 number of comparisons in the worst case. If the list already sorted, then it requires ‘n’ number of comparisons.

Worst Case : O(n2)
Best Case : Ω(n)
Average Case : Θ(n2)

 

Leave a Reply