Implementation of Insertion Sort

AIM:

          To write a C program to implement insertion sort

ALGORITHM:

            Step 1: Start the program.

            Step 2: The second element of an array is compared with the elements that

                        appears before it (only first element in this case). If the second element is

                        smaller than first element, second element is inserted in the position of

                        first element. After first step, first two elements of an array will be sorted.

Step 3: The third element of an array is compared with the elements that appears

 before it (first and second element). If third element is smaller than first

element, it is inserted in the position of first element. If third element is

larger than first element but, smaller than second element, it is inserted in

 the position of second element. If third element is larger than both the

elements, it is kept in the position as it is. After second step, first three

elements of an array will be sorted.

Step 3: Similarly, the fourth element of an array is compared with the elements

            that appears before it (first, second and third element) and the same

            procedure is applied and that element is inserted in the proper position.

            After third step, first four elements of an array will be sorted.

Step 4: If there are n elements to be sorted. Then, this procedure is repeated n-

            1 times to get sorted list of array

Step 5: Stop the program

PROGRAM

#include<stdio.h>

int main(){

int i,j,s,temp,a[20];

printf("Enter total elements: ");

scanf("%d",&s);

printf("Enter %d elements: ",s);

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

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

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

{

temp=a[i];

j=i-1;

while((temp<a[j])&&(j>=0))

{

a[j+1]=a[j];

j=j-1;

}

a[j+1]=temp;

}

printf("After sorting: ");

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

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

return 0;

}

OUTPUT

Enter total elements: 5

Enter 5 elements: 3 7 9 0 2

After sorting:  0 2 3 7 9

RESULT: Thus a C program is written to implement insertion sort and executed

                   successfully