insertion sort

                                       

   
                           INSERTION SORT

Definition: It is a simple and efficient sorting algorithm. Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. 

The analogy can be understood from the style we arrange a deck of cards. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put at their right place.

Algorithm For Insertion Sort:

INSERTION SORT(A):
   for i = 1 to n
    key ← A [i]
    j ← i – 1
  while j > = 0 and A[j] > key
    A[j+1] ← A[j]
    j ← j – 1
    End while 
    A[j+1] ← key
  End for 

C Program For Insertion Sort  On Code Blocks :
#include<stdio.h>
int main()
{
    int n,a[20],i,m,t;
    printf("How many number do you want to execute.");
    scanf("%d",&n);
    printf("Enter the elements one by one.");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<n;i++)
    {
        m=i;
        while(m>0 && a[m-1]>a[m])
        {
            t=a[m];
            a[m]=a[m-1];
            a[m-1]=t;
m--;
        }
    }
    for(i=0;i<n;i++)
        printf("%d  ",a[i]);
    return 0;

}
Output of the Program:

Example:

Time Complexity of Insertion Sort :

 If, we provide a sorted array to the insertion sort algorithm .It executes the outer loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.
For an unsorted array, it takes for an element to compare with all the other elements which mean every n element compared with all other n elements. Thus, making it for n x n, i.e., n2 comparisons. 

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)

By :Rani