What is Insertion Sort? explain with an example

Insertion sort

One element from the array is selected and is compared to the one side of the array and inserted to the proper position while shifting the rest of the elements accordingly.

Insertion algorithm

Insertion algorithm selects one element from start (position 2nd, C array index =1). It is saved to a temporary variable. Then it is compared to the left side elements one by one. If the element is bigger then the selected element, it is shifted to right. A hole is created while this shifting. Then this process is repeated till index reaches to first element. Element is not moved when value is less than the selected element. The hole is not shifted in this case. Now finally the selected element (from the temporary variable) is moved to hole. Now this element reached to its proper position. After this the next position or array index 2 is selected. Then we repeat the same process. Gradually all the left side elements are moved and becomes sorted. This entire process repeats till selection of array position goes to max (count-1). Finally entire array is sorted and selected element is inserted to its proper position.

 /* Insertion sort example code */

 void insertion_sort(int elements[], int count)

 {

   int selection, index;

   for(selection = 1; selection < count; selection++)

   {

     int tmp = elements[selection];

     for (index = selection; index > 0 &&

       tmp < elements[index - 1]; index--) /* compare */

     {

       elements[index] = elements[index - 1]; /*move */

     }

     /* insert it to the hole */

     elements[index] = tmp; /* insert */

   }

 }

Insertion sort example code

Code: Insertion Sort of 5 integer elements in ascending order.

 /* Insertion sort example */

 #include<stdio.h>

 int array[5] = { 4, 9, 5, 1, 0 };

 void print_aray(int elements[], int count)

 {

   for (int index = 0; index < count; index ++)

   {

     printf("%d, ",elements[index]);

   }

   printf("\n");

 }

 void insertion_sort(int elements[], int count)

 {

   int selection, index;

   for(selection = 1; selection < count; selection++)

   {

     int tmp = elements[selection];

     printf("Position #%d value %d\n",

            selection,

            elements[selection]);

     print_aray(elements, count);

     /* compare and shift */

     for (index = selection;

          index > 0 && tmp < elements[index - 1];

          index--) 

     {

       printf("move %d -> %d \n",

              elements[ index-1],

              elements[index]);

       elements[index] = elements[index - 1]; /*move right */

       print_aray(elements, count);

     }

     printf("insert @%d = %d\n",index, tmp);

     /* insert it to the hole */

     elements[index] = tmp; 

     print_aray(elements, count);

     printf("\n");

   }

 }

 int main(int argc, char *argv[])

 {

   printf("Insertion sort\n");

   print_aray(array, 5);

   insertion_sort(array, 5);

 }

Steps and Iterations (diagrams)

Output