# 8.9 – Insertion Sort

by on November 1, 2017

### Insertion Sort:

It is another method of sorting elements either in ascending or in descending order. Here in this method an element is selected and inserted in its actual position. The same procedure is continued from the second element to the last element. To have clear understanding, let us see a case in the insertion sort. In the array, 15, 20, 25, 30, 32 are in their appropriate positions. We need to place 23 (Key element) in its position. It is done in three steps

Storing the key element in a temp variable

```
temp=a[k];

```

Shifting the elements which are left side to the key element to their next positions as long as a[i]>temp. (32>23, 30>23, 25>23)
The actual position of key element is where the condition a[i]<=temp is true (20<=23) ```for(i=k-1;i>=0;i--)
{
if(a[i]<=temp)
break;
a[i+1]=a[i];   /* current element into the next element */
}
```

Now loop continue for i=4, 3, 2 but breaks when i is 1 and a[i]<=temp (20<=23) is true. The position of key element would be the next to a[i] that is a[i+1]. The key element, which was stored in temp is now assigned to its position a[i+1]

```a[i+1]=temp;
``` Procedure explained above is placing one element (key element) in its position. We do the same from second element (a) to the last element (a[n-1]). It can be done using a loop for k=1,2,3, ……..,n-1

```for(k=1;k<n;k++)
{
temp=a[k];              /* storing key element into temp */
for(i=k-1;i>=0;i--)
{
if(a[i]<=temp)
break;
a[i+1]=a[i];        /* current element into the next element */
}
a[i+1]=temp;           /* storing keyelelent in its position */
}
```

The above loop selects individual elements as key elements and places in their sorted position as loop progresses.

Program:

```#include<stdio.h>
int main()
{
int a,n,i,k,temp;
/* accepting elements into array*/
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
/* sorting the elements */
for(k=1;k<n;k++)
{
temp=a[k];                  /* storing key element into temp */
for(i=k-1;i>=0;i--)
{
if(a[i]<=temp)
break;
a[i+1]=a[i];           /* current element into the next element */
}
a[i+1]=temp;                /* storing keyelelent in its position */
}
/* printing the array elements */
printf("Elements in ascending order:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
return 0;
}
```

Execution:
How many elements?6
Enter 6 elements:
25  20  22  11  8  18
Elements in ascending order:
8   11   18   20   22   25

### Sorting array elements in descending order using insertion sort:

Program:

```#include<stdio.h>
int main()
{
int a,n,i,k,temp;
/* accepting elements into array*/
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
/* sorting the elements */
for(k=1;k<n;k++)
{
temp=a[k];  /* storing key element into temp */
for(i=k-1;i>=0;i--)
{
if(a[i]>=temp)
break;
a[i+1]=a[i];   /* current element into the next element */
}
a[i+1]=temp; /* storing keyelelent in its position */
}
/* printing the array elements */
printf("Elements in descending order:\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
return 0;
}
```

Execution:
How many elements?6
Enter 6 elements:
25  20  22  11  8  18
Elements in descending order:
25   22   20   18   11    8

Previous post:

Next post: