Program that implements the insertion sort method

Description: Insertion sort is similar to playing cards. To sort the cards in yourhand you extrat a card shift the remaining cards and then insert the extracted card in its correct place. The efficiency of insertion sort is O(n²).

Algorithm:

       ii) Insertion Sort:

1. start

2. for i= 1 to n increment in steps of 1

            begin

             assign k[i] to temp

3.         forj=i-1 down to j>=0 and temp<k[j]

             begin

              assign k[j] to k[j+1]

            end inner for loop

4.          assign temp to k[j+1]

            end for loop

5. stop

 Program:

#include<stdio.h>

main()

{

 int i,j,t,a[10],n,p=0;

clrscr();

printf("enter the range of array:");

scanf("%d",&n);

printf("enter elements into array:");

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

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

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

{

t=a[i];

for(p=i;p>0 && a[p-1]>t;p--)

a[p]=a[p-1];

a[p]=t;

}

printf("the sorted order is:");

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

printf("\t%d",a[i]);

getch();

}

*****  OUTPUT  *****

enter the range of array:5

enter elements into array:5

4

3

2

1

the sorted order is:    1       2       3       4       5

enter the range of array:6

enter elements into array:23

12

89

45

67          

34

the sorted order is:    12      23      34      45      67      89

conclusion: The program is error free

VIVA QUESATIONS

1)  Define insertion sort ?

Ans: Insertion sort is similar to playing cards. To sort the cards in yourhand you extrat a card shift the remaining cards and then insert the extracted card in its correct place.

2) Efficiency of the insertion sort ?

Ans: The efficiency of insertion sort is O(n²).