**Objective:** C program to sort the elements using insertion sort method

**Concept:** This uses decrease and conqueror method to sort a list of elements. This sorting technique is very efficient if the elements to be sorted are partially arranged in ascending order. Consider an array of n elements to sort. We assume that a[i] is the item to be inserted and assign it to item. Compare the item a[i] from position (i-1) down to 0 and insert into appropriate place.

**ALGORITHM :**

Insertionsort ( A [ 0…n-1 ] )

//Input: An array A [ 0….n-1 ] of orderable elements

//Output: Array A [ 0…..n-1 ] sorted in increasing order

Step 1: for i = 1 to n – 1 do {

Step 2: v = A[i]

Step 3: j = i – 1

Step 4: while j >= 0 and A[j] > v do {

Step 5: A[j+1] = a[j]

Step 6: j = j – 1

} //end while

Step 7: A[j+1] = v

} //end**Complexity:**

BEST CASE: n- Occurs when the elements are already sorted.

WORST CASE: n2- Occurs when the elements are sorted in descending order.

AVERAGE CASE: n2.

` ````
```#include
#include
int a[20] , n ;
void main ()
{
void insertionsort() ;
int i ;
clrscr () ;
printf ( " \n Enter size of the array : " ) ;
scanf ( "%d" , &n ) ;
printf ( " \n Enter the elements : \n " ) ;
for ( i = 0 ; i < n ; i++ )
scanf ( "%d" , &a[i] ) ;
insertionsort () ;
printf ( " \n The sorted elements are : " ) ;
for ( i = 0 ; i < n ; i++ )
printf ( "\n%d" , a[i] ) ;
getch () ;
}
void insertionsort ()
{
int i , j , min ;
for ( i = 0 ; i < n ; i++ )
{
min = a[i] ;
j = i - 1 ;
while ( j >= 0 && a[j] > min )
{
a[j + 1] = a[j] ;
j = j - 1 ;
}
a[j + 1] = min ;
}
}

=============Input - Output============= Enter size of the array : 5 Enter the elements : 9 2 8 5 1 The sorted elements are : 1 2 5 8 9