# C Program to Implement Insertion Sort

Insertion Sort is the common sorting algorithm that we commonly use while arranging cards. In this algorithm, the elements are compared with the rest of the elements of the array and inserted into a rightful (sorted) place after comparing.

## PsudeoCode:

Let be an array to be sorted and n be the size of the array. Then

``````InsertionSort(A,n)
{

for(i=1;i<n;i++)
{
temp=A[i];
j=i-1;
while(j>=0 && A[j]>temp)
{
A[j+1]=A[j];
j=j-1;
}
A[j+1]=temp;
}
}
``````

## Code in C:

``````#include<stdio.h>
#include<conio.h>

void InsertionSort(int[],int);

int main()
{
int i;
int n;
int a;
printf("How many numbers you want to sort: ");
scanf("%d",&n);

printf("\nEnter %d numbers: ",n);
for(i=0;i<n;i++)
{
printf("\nEnter %dth number: ",i+1);
scanf("%d",&a[i]);
}
InsertionSort(a,n);
getch();
return(0);
}

void InsertionSort(int a[],int n)
{
int temp;
int i;
int j;

for(i=1;i<n;i++)
{
temp=a[i];
j=i-1;
while(j>=0 && a[j]>temp)
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}

/*printing*/
printf("\nThe sorted array is: ");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}

``````

## Output:

Do comment down if you are confused in any steps.