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

// Замер времени
class timer {
	clock_t start;
	char buf[20];
public:
	timer();
	void init(); // начало замера
	const char* value(); // текущее значение
};

timer::timer()
{
	init();
}

void timer::init()
{
	start = clock();
}

// Вывод времени
const char* timer::value()
{
	clock_t t = clock() - start;
	int sec = t / CLOCKS_PER_SEC;
	if(sec > 1000) {
		sprintf(buf, "%.0f sec", (double)t / CLOCKS_PER_SEC);
	} else if(sec > 100) {
		sprintf(buf, "%.1f sec", (double)t / CLOCKS_PER_SEC);
	} else if(sec > 10) {
		sprintf(buf, "%.2f sec", (double)t / CLOCKS_PER_SEC);
	} else {
		sprintf(buf, "%.3f sec", (double)t / CLOCKS_PER_SEC);
	}
	return buf;
}

//******************************************************
// Размер тестового массива
#define TEST_SIZE 50000
//******************************************************

// Заполнение исходных данных
void init(int* arr)
{
	timer t;
	// Заполняем уникальными значениями
	for(int i = 0; i != TEST_SIZE; i++) arr[i] = i;
	// Перемешиваем
	int r = 54323; // ГСЧ с постоянной последовательстью
	for(int i = 0; i != TEST_SIZE; i++) {
		do {
			r = (r * 12347 + 1) % TEST_SIZE;
		} while(r < 0);
		
		int j = arr[i];
		arr[i] = arr[r];
		arr[r] = j;
	}
	printf("Init %u elements. %s\n", TEST_SIZE, t.value());
}

// Вывод содержимого массива
void print(const char* text, int* arr)
{
	printf(text);
	unsigned int check = 0;
	for(int i = 0; i < TEST_SIZE; i++) {
		if(i < 10) printf("%d ", arr[i]);
		check += i * arr[i];
	}
	printf(" sum %X\n", check);
}

// Решение перебором
void perebor(int* data, int* res)
{
	timer t;
	for(int i = 0; i < TEST_SIZE; i++) {
		for(int j = 0; j < i; j++) {
			if(data[j] > data[i]) res[i]++;
		}
	}
	printf("Perebor %s\n", t.value());
}

int main(int argc, char* argv[])
{

	int* data = (int*)calloc(TEST_SIZE, sizeof(int)); // массив исходных данных
	int* res = (int*)calloc(TEST_SIZE, sizeof(int)); // массив для результата
	if(!data || !res) {
		printf("No memory\n");
	} else {
		// Заполнение исходных данных
		init(data); 
		print("Data   ", data);
		// Расчет
		perebor(data, res); // менять на свое
		// Вывод результата
		print("Result ", res);
	}

	if(data) free(data);
	if(res) free(res);

	system("pause");
	return 0;
}