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

#define ALENGTH 2000

#include "random.h"
#include "insertion_sort.h"


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;
}