Insertion Sort
Insertion Sort
Insertion sort is another simple sorting algorithm which works by dividing the list in two parts, one being sorted and other being un-sorted. We pick elements from the unsorted part of the list and put it at the right place in the sorted part. This sorting algorithm uses the basic principle of progressively sorting the list by looking at each element one by one and placing it at the best possible place.
Insertion Sort will be better understood by the following example.
Let us consider the list :- 2 4 3 7 9 11 0
( 2 ) 4* 3 7 9 11 0 // 2 is already sorted we start by picking 4.
( 2 4 ) 3 7 9 11 0 // we compare 4 with the sorted list, and place it at the appropriate position
( 2 4 ) 3* 7 9 11 0 // Pick 3
( 2 3 4 ) 7 9 11 0 //Put in appropriate place
( 2 3 4 ) 7* 9 11 0 //Pick 7
( 2 3 4 7 ) 9 11 0 //Put 7 at appropriate place
( 2 3 4 7 ) 9* 11 0 //Pick 9
( 2 3 4 7 9 ) 11 0 //Put 9 at appropriate place
( 2 3 4 7 9 ) 11* 0 //Pick 11
( 2 3 4 7 9 11 ) 0 //Put 11 at appropriate place
( 2 3 4 7 9 11 ) 0* //Pick 0
( 0 2 3 4 7 9 11 ) //Put 0 at appropriate place
Now after looking at the example carefully, I think you got the gist of how this algorithm works. Its very simple involving only 2 things i.e. Picking the element from unsorted array and putting it in the sorted part. "Just like Card sorting works"
Now that we understood how insertion sort works, let us see how to code Insertion Sort in CPP.
CPP Program for Insertion Sort:
-By Sarvesh Bhatnagar
You might like:
