Insertion Sort

As the name suggests, insertion sort is a technique, which inserts an element at an appropriate location(in an array) by comparing each element with the corresponding elements present at its left and accordingly moves rest of the elements of the given array.

Insertion Sort Algorithm

Insertion sort time complexity

insertion sort implementation

#include <stdio.h>
#include <alloc.h>

int main()
{
  int *arr;
  int size;
  int i,j,k,n;
  printf("\nEnter array size: ");
  scanf("%d",&size);

  arr=(int*)calloc(size,sizeof(int));

  printf("\nEnter %d Values: ",size);
  for(i=0; i<size; i++)
    scanf("%d",&arr[i]);


  for(j=1;j<size;j++)
  {
     k=arr[j];
     for(i=j-1; i>=0&&k<arr[i] ;i--)
  arr[i+1]=arr[i];
     
     arr[i+1]=k;

  }
  printf("\nAfter sorting: ");
  for (i=0; i<size;i++)
     printf("%d ",arr[i]);
 free(arr);
 arr=NULL; 
 return 0;
}

Analysis

In insertion sort, we insert the element before or after and we start comparison from the first element. Since the first element has no other elements before it. So it does not require any comparison. The second element requires 1 comparison, third requires 2 comparisons. The fourth requires 3 comparisons and so on. The last element requires n-1 comparisons.