Insertion Sort Algorithm

Insertion Sort:-

Insertion sort algorithm has two case scenarios -

• Best case
• Worst case

1. In worst case the given array elements are arranged in reverse /decreasing order. Thus, we have to do 1 comparison in first pass, 2 in second and n-1 comparisons in (n-1)th  pass.Thus, the total no. of comparisons made will be equal to (n^2)/2 and the complexity will be O(n^2).
2. Best case is occurred when given list is already sorted. In this case we have to make only one comparison in each pass. So, the complexity will be O(n).

In both cases no. of  passes are (n-1).

where n is the no. of elements in given array.

Algorithm:-

int i,j,temp,x[n];

for(i = 1; i < n; i++)

{

            temp = x[i];

            j = i - 1;

            while( temp < x[j] && j >= 0)

            {

                       x[j + 1] = x[j];

                       j = j - 1;

            }

            x[j + 1] = temp;

}  

Example:-

              70 80 30 10 20

1. Split the array in two parts. One sorted list and second unsorted       list.

              70            80 30 10 20

          sorted              unsorted

2. Start placing elements in first list from second list at their correct     position.

              70  80           30  10  20

              

              30  70  80        10  20

              10  30  70  80      20

              10  20  30  70  80

The list is sorted now.