# C Program to Sort an Array Using Insertion Sort

Sorting is a procedure in which the given elements are arranged in ascending or descending order. For example if the elements of an array are –

5, 11, 15, 8, 7, 54, 63, 44

After sorting these elements in ascending order, the elements would be –

5, 7, 8, 11, 15, 44, 54, 63

What is Insertion Sort is :

Insertion sort proceeds by inserting each element at the proper place in a sorted list. This is the same technique used by card players for arranging cards. When they receive a card, they place it in the appropriate place among the cards that they have already arranged.

We will consider our list to be divided into two parts – sorted and unsorted. Initially the sorted part contains only the first element of the list and unsorted part contains the rest of the elements. In each pass, the first element from the unsorted part is taken and inserted into the sorted part at appropriate place. If there are n elements in the list, then after n-1 passes the unsorted part disappears and our whole list becomes sorted. Let’s see the c program to sort an array using insertion sort.

C Program ►►

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

void main()
{
int size,arr[100],i,j,k;

printf("Enter the Number of Elements : ");
scanf("%d",&size);

printf("\nEnter the elements of the Array : ");

for(int i=0;i<size;i++) {
printf("\nArray[%d] = ",i+1);
scanf("%d",&arr[i]);
}

/* Insertion Sort */
for(i=1; i<size ;i++)
{

k=arr[i];
/*k is to inserted at proper place in sorted part*/

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

arr[j+1]=k;

} // end of outside for

printf("\nSorted List is : \n");

for(i=0;i<size;i++)
printf("%d\t",arr[i]);

getch();

}
```

Explanation ►► In each iteration of for loop, first element of the unsorted part is inserted into the sorted part. The element to be inserted (arr[i]) is stored in the variable k. In the inner for loop, the sorted part is scanned to find the exact location for the insertion of element arr[i]. The search starts from the end of the sorted part so variable j is initialized to i-1. The search stops when we either reach the beginning of the sorted part or we get an element less than k. Inside the inner for loop, the elements are moved right one position, and obviously these are elements which are greater than k, At the end k is inserted at its proper place.