What is the use of insertion sort in data structure?

99 views
What is the use of insertion sort in data structure?
posted Nov 24, 2014

It is a simple sorting algorithm which sorts the array by shifting element one by one.Following are some of the important characteristics of insertion sort.

1-It has one of the simplest implementation.
2-It is efficient for smaller data sets, but very inefficient for larger lists.
3-insertion sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
4-It is better than selection sort and bubble sort algorithms.
5-Its space complexity is less, like bubble sorting, insertion sort also requires a single additional memory space.
6-It is stable, as it does not change the relative order of elements with equal keys
.

Sorting using Insertion Sort Algorithm:

``````int a [ 6 ] = { 5 , 1 , 6 , 2 , 4 , 3 } ;
int  i , j ,  key ;
for ( i=1; i < 6 ;   i + + )
{
Key= a [ i ];
j = i - 1;
while ( j > = 0  &&  key  < a [ j ] )
{
a [ j + 1 ] = a [ j ] ;
j - - ;
}
a [ j + 1 ] = key ;
}
``````