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

int main()
{
	int i, j;
	int n=100;
	int sr = 0, pr = 0;
	//scanf("%d", &n);
	int *arr = (int*)malloc(n* sizeof(int));
	srand(time(NULL));
	time_t start, end;
	start = time(NULL);
	//for (j = 0; j < 1000; j++)
	//{
		int step = n;
		for (i = 0; i < n; i++)
		{
			arr[i] =i ;
		}
		while (step > 1)
		{
			if (step > 1)
				step = step / 1.247;
			for (i = 0; (i + step) < n; ++i)
			{
				sr++;
				if (arr[i + step] > arr[i])
				{
					int tmp;
					tmp = arr[i];
					arr[i] = arr[i + step];
					arr[i + step] = tmp;
					pr++;
				}
			}
		}
		step = 1;
		for (i = 0; (i + step) < n; ++i)
		{
			sr++;
			if (arr[i + step] > arr[i])
			{
				int tmp;
				tmp = arr[i];
				arr[i] = arr[i + step];
				arr[i + step] = tmp;
				pr++;
			}
		}
//	}
	end = time(NULL);
	printf("\n");
	printf("time %f sec.\n", difftime(end, start));
	printf("\n");
	printf("%lf ", (sr));
	printf("\n");
	printf("%lf ", (pr));
	free(arr);
	return 1;
}