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

void insertionsort(int a[], int n);
int nrandom(int n);
int *make_data(unsigned int s, int n);

int main(void) {
	const int ns[3] = {10, 100, 1000};
	const int s = 666;
	int i;
	int n;
	int* a;
	
	for (i = 0; i < 3; i++) {
		n = ns[i];
		a = make_data(s, n);
		if (a == NULL) {
			return EXIT_FAILURE;
		}
		printf("n：%d\n", n);
		insertionsort(a, n);
		printf("\n");
		
		free(a);
	}
	return EXIT_SUCCESS;
}

void insertionsort(int a[], int n) {
	int i;
	int j;
	int e;
	int compareCount = 0;
	int assignCount = 0;
	
	for (i = 1; i < n; i++) {		
		assignCount++;
		e = a[i];
		
		for (j = i; 0 < j; j--) {
			compareCount++;
			if (a[j - 1] <= e) {
				break;
			}
		
			assignCount++;
			a[j] = a[j - 1];
		}
		
		assignCount++;
		a[j] = e;
	}

	printf("比較：%d回\n", compareCount);
	printf("代入：%d回\n", assignCount);
}

int nrandom(int n) {
	return rand() % n;
}

int *make_data(unsigned int s, int n) {
	int* a;
	int i;
	
	srand(s);
	
	a = calloc(n, sizeof(int));
	if (a == NULL) {
		return NULL;
	}
	
	for (i = 0; i < n; i++) {
		a[i] = nrandom(n);
	}
	
	return a;
}

n：10
比較：30回
代入：39回

n：100
比較：2655回
代入：2760回

n：1000
比較：242193回
代入：243195回