// The insertion method.
// This algorithm expands the sorted portion one by one
// by changing i as i=2, ..., n.
// temp is to keep the value of a[i].
// j scans the array portion a[1], ..., a[i-1] in reverse
// order to find the the position for temp. As long as a[j]>temp,
// it is shifted one place right.
#include <stdio.h>
#include <math.h>
main()
{ int i,j,k,n,temp,t;
  int a[10000];
  printf("input size \n");
  scanf("%d",&n);
  /*for (i=1;i<=n;i++) { scanf("%d",&a[i]);};*/
  for (i=1;i<=n;i++) a[i]=random()%1000;
  for (i=1;i<=10;i++) { printf("%d ",a[i]);}
  printf("\n");
  t=clock();
  for (i=2;i<=n;i++)
  { 
    temp=a[i]; 
    for (j=i-1;j>=1;j--)
      if (a[j]>temp) a[j+1]=a[j]; 
                     else break;
    a[j+1]=temp; 
  };
  for (i=1;i<=10;i++) { printf("%d ",a[i]);}
  printf("\ntime= %d millisec\n",(clock()-t)/1000);
}