# Insertion sort

## Working of Insertion sort

Insertion sort is sorting mechanism which is best then both bubble sort and selection sort. The elements in the array are compared with the preceding elements.

In insertion sort array zeroth element is declared to be the sorted element, next element(first index) assume it as a key element, it is compared with its preceding elements one by one If any element in the preceding elements found to be greater than the key element then the key element will be shifted to the greater element index place and the greater element and its next elements move one step right(the index number of the greater element and its next elements will be increased by 1).

- here, in the example above 7 is declared to be sorted, so the comparison will start from the next element 6
- In step1, the 1st index element 6 is compared with the left side values in its array and takes its respective place after comparing the values of left side array elements
- In step2, the 2nd index element 5 is compared with its left side elements and will be inserted in its appropriate place
- Likewise, the iterations will be done until all elements in the array are sorted

## The Time complexity of Insertion Sort

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

## Program for Insertion sort

#include<stdio.h>

void insertionsort(int a[],int n)

{

int j,p;

int tmp;

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

{

tmp=a[p];

for(j=p;j>0 && a[j-1] > tmp; j--)

a[j]=a[j-1];

a[j]=tmp;

}

}

int main()

{

int i,n,a[10];

printf("enter no of elemnts");

scanf("%d",&n);

printf("enter the elemnts ");

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

{

scanf("%d",&a[i]);

}

insertionsort(a,n);

printf("the sorted elements are");

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

printf("%d",a[i]);

printf("\n");

return 0;

}