Insertion Sort In Data Structure

    ⇰  INSERTION SORT :-

Insertion sort  is one of the simplest method to sort an array. This is an in-place comparison-based sorting algorithm. The array is searched sequentially and unsorted items are moved left or right side according to order we want to sort. This sorting algorithm is not suitable for large data. Its average and worst case complexity is  Ο(n2), where n is the number of items in an array. 
     An example of insertion sort occurs in everyday life is while playing cards. Ones hand extract the card, and then shift the remaining cards and then insert the extracted card in the correct place. This process is repeated until all the cards are in the correct position or in correct sequence.


  FOR EXAMPLE :- 

   Let us take an unsorted array:-

                3 7 4 1 8 2

now the insertion sort technique compare the 1st element of array to 2nd element, if sequence or order is not correct then corrects it. 

               3 7 4 1 8 2

Comparing the 1st to 3rd element, if sequence or order is not correct then corrects it. 

               3 4 7 1 8 2

Comparing the 1st  to 4th element, if sequence or order is not correct then corrects it. 

              1 3 4 7 8 2

Compare the 1st  to 5th element, if sequence or order is not correct then corrects it. 

              1 3 4 7 8 2

Compare the 1st element of array to 5th element, if sequence or order is not correct then corrects it. 

              1 2 3 4 7 8

Hence at last array is in sorted order.

⇰ ALGORITHM OF INSERTION SORT :-

variable used:- L=list of array, n= no. of element in list, 
           I, J, temp = local variable  

Step1 :- Initialize 
              I = 1
Step2 :- Repeat through step3 to step5 while I<n.

Step3 :- temp = L[I] 
             J=I-1

Step4 :- Repeat while ( J>=0 and temp <L[j] )
             L [J+1] = L[J]
             J = J+1

Step5 :- L[ J+1] = temp
              I =I+1

Step6 :- Exit.



⇰  PROGRAM OF INSERTION SORT IN 'C' :-

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

void main()

{

    int  i, j, temp, l[5];

 printf("Enter Values of array for sorting:- ");

for (i = 0 ; i < 5 ; i++)

{

  scanf ( " %d " ,& l[i] );

}

for (i = 1 ; i < 5 ; i++)

 {

   temp= l[i];

   for(  j=i-1;  j >=0  && temp < l[j] ; j-- )

    {

       l[ j+1] = l[j]; 

    }

     

   [ j+1] =temp;

 }

printf(" \n Sorted value :- ");

for ( i=0 ; i < 5; i++)

{

 printf(" \n %d" , l[i] );

}

getch();

}

Share, Follow and please comment if you find anything incorrect or to share more information about the topic discussed above.