CONCEPT OF INSERTION SORT - DATA STRUCTURE

In insertion sort newly inserted element are placed to their sorted location.

Suppose , if we want to insert 5 elements into required space or place and ( 0 , 1 , 2 , 3 , 4 ) are their index or location where the element are stored. Now we first check the space whether it is require for inserting element or not.If space is required.

                    

Suppose we want to insert first element such as (15) , than we first check space at 0th location , if space is available than (15) is stored in 0th location.

In second time we want to insert (10) , than we check the condition, whether the previous right most element (15) is  greater than (10) or not. If it is true than (15) is swapped in next location that is (1) and (10) is stored in 0th location.

In third time we want to insert (5) than we check the condition whether the previous right most element (15) is greater than (5) or not , if it is true than (15) is swapped in next location i.e (2) and space is required for (5) but before store in location (2) , we again check with the right most element i.e (10) , whether it is greater than (5) or not.If it is true than (10) will be swapped into next location i.e (1) and (5) is stored in 0th location.

     

In this way we insert the further elements such as (13) & (17) from above example.

           

ALGORITHM OF INSERTION SORT:

Algorithm Insertionsort  (A , N)

A is an array with N elements.

STEP 1  : FOR I = 0 TO N - 1 DO

STEP 2  : K = I - 1

STEP 3  : READ X

STEP 4  : WHILE K > = 0  AND  A [K] > X

STEP 5  : A[ K + 1] = A[K]

STEP 6  : K= K + 1

STEP 7  : END WHILE

STEP 8  : A[ K + 1] = X

STEP 9  : NEXT I

STEP 10: END

PROCEDURE OF INSERTION SORT:

void Insertionsort sort ( int a[50] , int n )

{

        int i , k , x ;

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

        {

                k = i - 1;

                printf ( " Enter x: " ) ;

                scanf ( " % d " , & x ) ;

                while ( k >=0 && a[k] > x)

                {

                    a [ k + 1 ] = a[k] ;

                    k - - ;

                }

                a [ k + 1] = x ;

        }

}

Note , here (k)  point to right most element.

LOGIC DIAGRAM

EVALUATION OF INSERTION SORT:

For evaluation of insertion sort their are two cases :

1. Best Case Complexity for Insertion Sort :

Best case for insertion sort occur when newly inserted element is greater than all array element than (N) element needs only (N-1) comparison one for each (N-1) elements and zero for first elements with complexity beg O of (n).

2. Worst Case  Complexity for Insertion Sort :

Worst case for insertion sort occur when newly inserted element is less than all array elements.

To insert 1st element insertion sort need 0 compassion.  

To insert 1st element insertion sort need 1 compassion.  

To insert 1st element insertion sort need 2 compassion.  

To insert 1st element insertion sort need 3 compassion. 

-                        -

-                        -

-                        -

To insert 1st element insertion sort need (n - 1) compassion.  

--------------------------------------------------------------------------

Total  =  n (n - 1) / 2

--------------------------------------------------------------------------

fn =  n2 / 2  - n / 2  

Ofn =  O(n2)