Insertion Sort

Input: sequence of n nos a1,a2,a3…
Output: permutation of those numbers such that a1′<=a2′<=a3′..
It’s an effective algo for sorting small no of elements.

Find the correct position and the insert it
To find the correct position we compare with the nos already present
Check with each element. The whole array would be sorted after the process. i.e, check with each element and insert it before or after.

So It takes in i/p an array of n elements A[1-n] in sorted order
During insertion, the nos are rearranged within the array and sorted.


void insertion_sort(int unsorted[],int number_of_elements)
{
 int i,j,key;
 for(j=2;j&lt;=number_of_elements;j++)
 {
key=unsorted[j];
i=j-1;
while(i>0 && unsorted[i]>key)
{
unsorted[i+1]=unsorted[i];
i=i-1;
}
unsorted[i+1]=key;
}
}

Just an example
5 | 2 | 4 | 6 | 1 | 3 |
Key = 2 unsorted[j]
unsorted[i]>key, 5>2
unsorted[i+1]=unsorted[i], unsorted[2]=unsorted[1]=5
i=i-1=0, unsorted[i+1]=key=2

2 | 5 | 4 | 6 | 1 | 3 |
2 | 4 | 5 | 6 | 1 | 3 |
1 | 2 | 4 | 5 | 6 | 3 |    in loop. Checks with all previous elements
1 | 2 | 3 | 4 | 5 | 6 |

Complete implementation can be found at https://github.com/sowmyaravidas/Sorting-Algorithms

Advertisements

Tagged: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s