Insertion Sort Algorithm in CLRS and Robert Sedgewick

Question

In Online Course of Algorithms by Robert Sedgewick, Insertion sort is described as -

for(i = 0; i< length of array ; i++) // *i represents pointer which increments uniformly*
    for( j = i ; j > 0 ; j--) // *j is subpart of i which compares previous elements*  
        if( array[j] <  array[j-1]) 
              swap( array[j] , array[j-1] ) ;
        else
           break;

in CLRS book , it is shown as -

for(i=2; i< length of array; i++)
    key_value = array[i] ;
    j = i-1 ;
    while( j > 0 && array[j] > key_value)
        array[j+1] = array[j]
        j = j-1
    array[j+1] = key_value

My question is - These 2 code are similar or different???

Answer 1

They are totally the same in concept.

In insertion sort, we always assume that we have a sorted part in our array, and we try to add a new item one by one to that sorted part. So we need to find the position of the new item.

2 5 7 12 17 23 4 68 1 32 19 56 32 16 89 110 70 89 12 72 99 8
-------------- ----------------------------------------------
  Sorted part   New items to be added to the sorted part

Note that initially, we assume that the first item is sorted, and start from the second item to add to the sorted part.

In both cases, you have a main loop that iterates over all items to insert to the sorted part one by one, and another loop tries to find the position of the new item. However, one of the algorithms uses a for loop and another one uses a while loop in order to find the position to add the new item.

Note that as we are working with arrays here, we need to shift items to insert the new item in the right place. In the Robert Sedgewick version, it swaps the item with previous elements immediately, and In the CLRS version, it only shift items to the right one by one and when it found its place it puts the new item in there.