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<stdio.h>
#include<conio.h>
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