#include <stdio.h>
#include <stdlib.h>

#define ALENGTH 2000

int insertion_sort(double*, int);
double rand_unif();
int insertion_sort_random(double *A, int n);

double rand_unif() 
{
    return (1.0 * random()) / RAND_MAX;
}

/* int main() */
/* { */
/*     int i, c; */
/*     double x[ALENGTH]; */
/*     srandom(time(NULL)); */
/*     for (i = 0; i < ALENGTH; i++) x[i] = rand_unif(); */
/*     /\* printf("\nBefore sorting:\n\n"); *\/ */
/*     /\* for (i = 0; i < ALENGTH; i++) printf("%f\n", x[i]); *\/ */
/*     /\* printf("\nAfter sorting:\n\n"); *\/ */
/*     c = insertion_sort(x, ALENGTH); */
/*     /\* for (i = 0; i < ALENGTH; i++) printf("%f\n", x[i]); *\/ */
/*     printf("%d\n", c); */
/*     return 0; */
/* } */

int main()
{
    int r, n;
    double x[ALENGTH];
    srandom(time(NULL));
    for (n = 100; n < ALENGTH; n = n + 10) {
	for (r = 0; r < 10; r++) {
	    printf("%d,%d\n", n, insertion_sort_random(x, n));
	}
    }
    return 0;
}


int insertion_sort_random(double *A, int n) 
{
    int i;
    for (i = 0; i < n; i++) A[i] = rand_unif();
    return insertion_sort(A, n);
}


int insertion_sort(double *A, int n)
{
    int i, j, count = 0;
    double key;
    for (j = 1; j < n; j++) {
	key = A[j];
	i = j-1;
	while (i > -1 && A[i] > key) {
	    count++;
	    A[i+1] = A[i];
	    i = i-1;
	}
	A[i+1] = key;
    }
    return count;
}