Insertion Sort :
In insertion sort method every element is put or inserted at its proper position. For this first the position of the element is found and then inserted at that position by moving all the previous elements by one position down. Position to be inserted is found by compared it with all its previous elements in the array. Let us consider an array ‘A’ containing 6 elements.
Let A[6] = {25, 10 , 35, 16, 40, 30 } which needs to be sorted in descending order.
We begin with the second element assuming that first element is at its proper position. Hence, the 2nd element a[1] is compared with the 1st element a[0]. i.e. 10 is compared with 25. We find A[1] < A[0] i.e. 10 < 25, therefore 10 is already in a correct position.
Array status will therefore remain as it is : a[6] = {25,10,35,16,40,30}
Next the 3rd element i.e. 35 is compared with 1st & the 2nd element i.e. 35 is compared with 25 and 10. Since A[2] > A[0] i.e. 35 > 25 hence 35 to be inserted at 1st position ( at A[0] ), For insertion the 1st element is moved to the 2nd ,position, the 2nd element is moved to the 3rd position and then the element 35 is inserted at 1st position
Array A[6] = { 25, 10 , 35 , 16 , 40 , 30}
↑_____↓ (35 to be inserted at position )
Array status at this stage : A[6] = {35,25,10,16,40,30}
Next the 4th element is compared with the first three elements one by one, and then inserted at its proper position which is the 3rd position .
Array A[6] = { 35 , 25 , 10 , 16 , 40 , 30 }
↑___↓ (16 to be inserted at position 3)
Array status after the inserting 16 : A[6] = {35,25,16,10,40,30}.
Similarly the 5th element is compared with the previous four elements and
inserted at its proper position i.e. the 1st position and the elements from
1st position to 4th position are moved down by one position
Array A[6] = { 35 , 25 , 16 , 10 , 40 , 30 }
↑_____________↓ (40 to be inserted at position 1)
Array status after inserting 40 : A[6] = {40,35,25,16,10,30}
Finally the last (6th ) element (30) is compared with its previous five
elements and inserted at the proper position which is the 3rd position :
Array A[6] = { 40 , 35 , 25 , 16 , 10 , 30 }
↑_________↓ ( 30 to be inserted at position 3)
Array status after the inserting 30
A[6] = { 40 , 35 , 30 , 25 , 16 , 10 } Is Now SORTED