Insertion Sorting in C Language.

Keep in mind:-

1. Take one element at a time for sorting (i.e. one by one).
2.  Useful for sorting small data set (not used this sorting for large data sets).
3. Time complexity is Worst case =O(n2)..
4. Time complexity depend on number of compare + number of movement.
5. Sometime calls as In-Place Algorithm.
6. It may be ascending or descending orders.

Basic Idea:-

If you have 4 cards (numbering 4,3,7,1).
          Before sorting :- 4,3,7,1.
           After sorting :-   1,3,4,7.

Process:-
1. Take first card (i.e. 4).
2.  Take another card 3 compare with first one, we got 4>3. So move 3 before 4.
3. Take 3rd card 7 compare with previous one 4, we got 7>4. So no need to sorting,
4. Take 4th card 1 compare with previous one 7, we got 1<7. So move one place left, again 1<4 move      left, again 1<3 move left. Therefore 1 comes at their position.
Sorting Done.

Algorithm:-

Insertion_sort(A)
{
      for i=2 to A.length
          temp = A[i]
            j = i-1
  while( j > 0 and A[j] > temp)
{
A[j+1] = A[j]
   j=j-1
}
A[j+1] = temp
}


C coding:-

#include<stdio.h>
void main()
{
int i,j,n,temp,a[100];
clrscr();
printf("Enter the number of element for sorting \n");
scanf("%d",&n);
printf("%d to be element", n);
for(i>0;i<n;i++)
      {
         scanf("%d",&a[i]);
    }

for(i>1;i<n;i++)
     {
         temp=a[i];
          j= i-1;
             while(j>1 && temp<a[j])
             {
                    a[j+1]=a[j];
                    j=j-1; // --j;
             }
a[j+1]=temp;
}
printf("after sorting \n");
for(i>0;i<n;i++)
printf("%d",a[i])
getch();
}

Output:-

Enter the number of element for sorting
5
5 to be element 2
4
1
6
7
after sorting
1 2 4 6 7