# Insertion sort in C

In **insertion sort** what happens is, we assume the first element of the array as already sorted. Then we take the next element and compare it with the previous element and place it accordingly depending if it is greater or smaller compared to the previous element. Now the first two elements are sorted .Now, we take the third element and place it accordingly and so on…

**For example: [7,1,5,3,6]**

1st pass: [7,1,5,3,6] ‘7’ is already sorted.

2nd pass: [1,7,5,3,6] ‘1,7’ are sorted.

3rd pass: [1,5,7,3,6] ‘1,5,7’ are sorted.

4th pass: [1,3,5,7,6] ‘1,3,5,7’ are sorted.

5th pass : [1,3,5,6,7] all the elements are sorted now

#include void main() { int n,i; int a[100]; printf("enter no. of elements\n"); scanf("%d",&n); printf("enter the elements\n"); for(i=0;i<n;i++) { scanf("%d",&a[i]); } printf("array before sorting:\n"); displ(a,n); insort(a,n); printf("array after sorting:\n"); displ(a,n); } void displ(int a[],int n) { int i; for(i=0;i<n;i++) { printf("%d ",a[i]); } printf("\n"); } void insort(int a[],int n) { int i,j,temp; for(i=1;i=0) { a[j+1]=a[j]; j--; } a[j+1]=temp; } }

**OUTPUT**:

enter no. of elements

5

enter the elements

12 3 4 0 1

array before sorting:

12 3 4 0 1

array after sorting:

0 1 3 4 12