Insertion sort

Program:

/***  insertion sort function   ***/
#include<stdio.h>
void insertionsort(int a[],int size);
#define MAX 10
int main()
{
         int a[MAX];
         int i;
         printf("enter %d elements:: ",MAX);
         for(i=0;i<MAX;i++)                     /** read the numbers to be sorted  **/
         scanf("%d",a+i);
         int length=MAX;
         insertionsort(a,length);              /**   function call  **/
         for(i=0;i<MAX;i++)                   /** print numbers in non-decreasing order **/
         printf("%d ",*(a+i));
         return 0;
}
void insertionsort(int a[],int size)
{
         int i,j,key;
         for(i=1;i<size;i++)
         {
                key=a[i];
                j=i-1;
               while((key<a[j])&&(j>=0))
               {
                     a[j+1]=a[j];
                     a[j]=key;
                      j--;
                }
          }
          return;
}

 

Sample input:

1 4 6 5 2 3 7 4 8 9

Output:

1 2 3 4 4 5 6 7 8 9

 

Algorithm:

 

for i=1 to length of array
                key=a[I]
                j=i-1
               while(key<a[j])AND(j>=0)
                     a[j+1]=a[j]
                     a[j]=key
                      j--

return array.