#include <stdio.h>
 
int comp = 0;
int swap = 0;
 
/* 挿入ソート*/
void insertion_sort(int a[], int n){
int i,j,t;
for(i=1; i<n; i++){
t = a[i];
comp++;
j=i;
while(j>=1 && ++comp && t < a[j-1]){
a[j] = a[j-1];
j--;
swap++;
comp++;
}
a[j] = t;
}
} 
 
int main(void) {
	int a[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
	insertion_sort(a, 10);
 
	printf("nr_comp=%d nr_swap=%d\n", comp, swap);
	for(int i=0; i<10; i++) {
		printf("%d: %d\n", i, a[i]);
	}
	return 0;
}
 
 

I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgY29tcCA9IDA7CmludCBzd2FwID0gMDsKCi8qIOaMv+WFpeOCveODvOODiCovCnZvaWQgaW5zZXJ0aW9uX3NvcnQoaW50IGFbXSwgaW50IG4pewppbnQgaSxqLHQ7CmZvcihpPTE7IGk8bjsgaSsrKXsKdCA9IGFbaV07CmNvbXArKzsKaj1pOwp3aGlsZShqPj0xICYmICsrY29tcCAmJiB0IDwgYVtqLTFdKXsKYVtqXSA9IGFbai0xXTsKai0tOwpzd2FwKys7CmNvbXArKzsKfQphW2pdID0gdDsKfQp9IAoKaW50IG1haW4odm9pZCkgewoJaW50IGFbXSA9IHsgMTAsIDksIDgsIDcsIDYsIDUsIDQsIDMsIDIsIDF9OwoJaW5zZXJ0aW9uX3NvcnQoYSwgMTApOwoJCglwcmludGYoIm5yX2NvbXA9JWQgbnJfc3dhcD0lZFxuIiwgY29tcCwgc3dhcCk7Cglmb3IoaW50IGk9MDsgaTwxMDsgaSsrKSB7CgkJcHJpbnRmKCIlZDogJWRcbiIsIGksIGFbaV0pOwoJfQoJcmV0dXJuIDA7Cn0KCg==