Insertion Sort

2. Then we will start comparing from our first element “6“of unsorted subarray with the most rightmost element “10“in the sorted array first then with the second element and so on till we get whole sorted array. As currently one element is present in it so we just compare with 10. Also we will store the 10 is some temporary variable say “pick_num”. So 10 is greater than 6 we will place it one step forward towards 6 Then sorted array becomes:

3. Pick next element from unsorted array which is 22 so update “pick_num” variable value to 22, compare with the rightmost element 10. As 22 is already greater than 10 no need to change the position. Again 22 is compare with 6 also. As 22 is greater no need to change. So our sorted array becomes:

4. Next element from unsorted is 2 so update “pick_num” variable value to 2. Compare with the rightmost element which is 22. As 22 is greater so their position should be interchanged but we will not do this. Of course we will increment or move 22 one direction forward toward the right direction as shown below:

But value 2 will not place at the old position of 22 which is index 2 at this moment. Instead we search for the right position for 2 in the sorted array. That’s why it has been called insertion sort because we insert the element in such order that the array remain sorted.

Then 2 is compare with 10 as 10 is greater so it will be shifted towards right direction but again we will not place the 2 at the position of 10. Array becomes:

Then 2 is compare with 6 as 6 is greater so it will be shifted towards rightmost direction but 2 still will not place at position or index of 6.

As we have reached the 0 index which means no more elements left to compare also 2 is smaller among the elements in the sorted array so this is the right place for our element 2. Here we go and the array becomes:

We will follow same steps 1 to 4 for all when we pick other elements from the unsorted array.

Insertion Sort Program

<?php

$array= [10,6,22,2,15,87,55] ;
$a = array();
for($i=1 ; $i<= count($array)-1;$i++){
    $pick_num = $array[$i];
    $j = $i- 1;
     
    while($j>=0 && $array[$j] > $pick_num){	
        $array[$j+1]  = $array[$j] ;
        $j--;
    }
    $array[$j+1] = $pick_num;

}
//echo count($array);
for($i = 1 ;$i <= count($array); $i++){
    echo $array[$i]."\n";
}


?>

#include<stdio.h>

void main(){

    int length, array[100], n, pick_num ,i,j;

    //printf(" print %d",length);
    printf("Enter the size of array\n");
    scanf("%d",&length);
    printf("Enter the %d elements\n",length);

    for(i=0 ;i<length; i++){
        scanf("%d",&array[i]);
    }

    for(i=1;i< length;i++){
        pick_num = array[i] ;
        j = i-1;    // compare with previous 0 index element
        while(j>=0 && array[j] > pick_num){
            array[j+1] = array[j];

            // as we have to keep back trace to look for right position in the sorted array.
            j--;  
        }
        array[j+1] = pick_num ;
    }
    printf("Sorted elements\n");
    for(i=0 ;i<length; i++){
        printf("%d\n",array[i]);
    }
}