#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <time.h>
#include <random>
#include <string>
#include <algorithm>
using namespace std;

template <typename x>
void Sort_insert(x*a, int n)
{
	srand(time(0));
	unsigned int start = clock();
	int j;
	for (int i = 1; i < n; i++)
	{
		j = i;
		while (a[j - 1] > a[j] && j > 0)
		{
			swap(a[j - 1], a[j]);
			j--;
		}
	}
	unsigned int end = clock();
	cout << "Время выполнения Sort_Insert: " << double(end - start) / 1000 << endl;
}

template <typename x>
void ShellSort(x*a, int n)
{
	srand(time(0));
	unsigned int start = clock();
	int i, j, step;
	x tmp;
	for (step = n / 2; step > 0; step /= 2)
		for (i = step; i < n; i++)
		{
			tmp = a[i];
			for (j = i; j >= step; j -= step)
			{
				if (tmp < a[j - step])
					a[j] = a[j - step];
				else
					break;
			}
			a[j] = tmp;
		}
	unsigned int end = clock();
	cout << "Время Выполнения Shell_Sort : " << double(end - start) / 1000 << endl;
}

struct student
{
	string name, surname;
	int marks[5];

	bool operator < (student b)
	{
		if (surname != b.surname)
			return surname < b.surname;
		else return name < b.name;
	}

	bool operator > (student b)
	{
		if (surname != b.surname)
			return surname > b.surname;
		else return name > b.name;
	}

	bool operator == (student b)
	{
		return name == b.name && surname == b.surname;
	}


	void print()
	{
		cout << surname << " " << name << " ";
		for (int i = 0; i < 5; i++)
			cout << marks[i] << " ";
		cout << endl;
	}
};

void random_students(student*c, student*c1, student*c2, int n)
{
	string names[] = { "Andrey", "Sergey", "Nastya", "Alena", "Misha", "Sasha", "Vanya","Elena" };
	string surnames[] = { "Brown", "Green", "Yellow", "Black", "White", "Vaselenko", "Poroshenko", "Glinko", "Vasilisko", "Potter", "Portenko" };
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		c[i].name = names[rand() % 8];
		c1[i].name = c[i].name;
		c2[i].name = c[i].name;
		c[i].surname = surnames[rand() % 11];
		c1[i].surname = c[i].surname;
		c2[i].surname = c[i].surname;
		for (int j = 0; j < 5; j++)
		{
			c[i].marks[j] = 1 + rand() % 5;
			c1[i].marks[j] = c[i].marks[j];
			c2[i].marks[j] = c[i].marks[j];
		}
	}

}

void random_numbers(int*a, int* a1, int* a2, int n) //рандом чисел
{
	srand(time(NULL)); // инициализируем рандом

	for (int i = 0; i < n; i++)
	{
		a[i] = (rand() % RAND_MAX);
		a1[i] = a[i];
		a2[i] = a[i];
	}
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;

}

void random_string(string*b, string* b1, string* b2, int n)    //рандом стринга
{
	srand(time(0));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < 1 + rand() % 5; j++)
		{
			b[i] += 97 + rand() % 25;
			b1[i] = b[i];
			b2[i] = b[i];
		}
	for (int i = 0; i < n; i++)
		cout << b[i] << " ";
	cout << endl;
}

template <typename r>
void printt(r*a, int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
}

int main()
{
	setlocale(LC_CTYPE, "Russian");
	int n;
	cin >> n;
	int* a = new int[n];
	int* a1 = new int[n];
	int* a2 = new int[n];
	string* b = new string[n];
	string* b1 = new string[n];
	string* b2 = new string[n];
	student* c = new student[n];
	student* c1 = new student[n];
	student* c2 = new student[n];

	random_numbers(a, a1, a2, n);
	random_string(b, b1, b2, n);
	random_students(c, c1, c2, n);
	for (int i = 0; i < n; i++)
		c[i].print();
	cout << endl;

	cout << "Сортировка чисел: " << endl;
	Sort_insert(a, n);
	ShellSort(a1, n);

	double time = clock();
	sort(a2, a2 + n);
	cout << "Время Выполнения STL_Sort : " << (clock() - time) / CLOCKS_PER_SEC << endl;
	cout << endl;

	cout << "Сортировка строк:" << endl;
	Sort_insert(b, n);
	ShellSort(b1, n);
	time = clock();
	sort(b2, b2 + n);
	cout << "Время Выполнения STL_Sort : " << (clock() - time) / CLOCKS_PER_SEC << endl;
	cout << endl;

	cout << "Сортировка студентов:" << endl;
	Sort_insert(c, n);
	ShellSort(c1, n);
	time = clock();
	sort(c2, c2 + n);
	cout << "Время Выполнения STL_Sort : " << (clock() - time) / CLOCKS_PER_SEC << endl;
	cout << endl;

	/*printt(a, n);
	cout << endl;
	printt(a1, n);
	cout << endl;
	printt(a2, n);
	cout << endl;
	printt(b, n);
	cout << endl;
	printt(b1, n);
	cout << endl;
	printt(b2, n);
	cout << endl;
	for (int i = 0; i < n; i++)
		c[i].print();
	cout << endl;
	for (int i = 0; i < n; i++)
		c1[i].print();
	cout << endl;
	for (int i = 0; i < n; i++)
		c2[i].print();*/

	return 0;
}