8.9 – Insertion Sort

by subbu on November 1, 2013

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.

Array elements

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)

Key element - insertion sort

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].

shifting elements insertion sort

The key element, which was stored in temp is now assigned to its position a[i+1]

a[i+1]=temp;

placing element at its position

Procedure explained above is placing one element (key element) in its position. We do the same from second element (a[1]) 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[50],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[50],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: