#include <stdio.h>
#include <time.h>
#define MAX_SIZE 5001
#define SWAP(x,y,t) ((t)=(x), (x) = (y), (y) = (t))
void insert(int e, int a[], int i)
{
a[0]=e;
while(e < a[i])
{
a[i+1] =a[i];
i--;
}
a[i+1] = e;
}
void insertionSort(int a[], int n)
{
int j,temp;
for(j=2; j<=n; j++){
temp= a[j];
insert(temp, a, j-1);
}
}
void main()
{
int i,n,step = 500;
int a[MAX_SIZE];
double duration;
for(i=1; i<=10; i++)
{
a[i] = rand();
}
printf(" n time\n");
for(n=0; n<=5000; n+=step)
{
clock_t start = clock();
long repetition= 0;
do
{
repetition++;
for(i=0; i<n; i++)
a[i] =n-i;
insertionSort(a, n);
}while(clock() -start <1000);
duration = ((double) (clock() -start))/CLOCKS_PER_SEC;
duration/=repetition;
printf("%6d %f\n", n,duration);
if(n==1000) step =1000;
}
}