Algorithms lesson 1

Yesterday i read insertion sort from this book, 'Introduction to Algorithms' by cormen. Great book. Today i am executing in C programming language.

The main theory of insertion sort is that

for example if we have an array of unsorted numbers, our goal is sort by insertion sort.

so first we sort from the left, that means first we take 1 number to be sorted, next we make two numbers from left sorted, then 3 and so on till the length of the array to the right.

since 1st element is sorted if sorted array length is 1

The best way to explain insertion is by deck of cards. take n cards which are unsorted in your right hand.

we pick the left most card, and put it in the left hand.
the cards in the left hand are always sorted.

then we again pick the left most card from right hand and put it in left hand, such that the right hand cards are sorted. sometimes we have to shift the positions of the cards to the right, such that the smallest card is on the left most side
But in here, we are sort inside the array, so we are creating a subarray we finally after sorting spans the whole length of the array.

This is my C code:

#include <stdio.h>

int main(){
  int arr[6]={23,1,43,22,756,12};
  int i,j,k, key;

  for ( j =1;j<6; j++){
      key=a[j];                       // we are storing the left most element for the subarray
      i=j-1;                            // we are making 'j' as the length of subarray which is always sorted
      while( i>=0 && a[i]>key){              // we are entering the subarray here
         k = a[i];
         a[i] = a[i+1];                 // we are swapping left and right, since the left > right
         a[i+1]=k;
         i=i-1;
       }
       a[i+1] = key;               // when the loop exits we don't left element changed, so here we are changed
      }
   return 0;
}