Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
9.0 kB
2
Indexable
Never
#include <iostream>
#include <ctime>

template <typename type>

class Vector
{
private:
	int size;
	type* vector;
public:
	Vector()
	{
		vector = nullptr;
		size = 0;
	}
	Vector(int size_vector)
	{
		this->size = size_vector;
		if (size >= 0)
		{
			vector = new type[size];
			for (int i = 0; i < size; i++)
			{
				vector[i] = 0;
			}
		}
		if (size < 0)
		{
			throw ("Размер массива меньше 0");
		}
	}
	~Vector()
	{
		delete[] vector;
	}
	int getSize()
	{
		return size;
	}
	void resize(int size_vector)
	{
		if (size_vector >= 0)
		{
			type* vector_vector = new type[size_vector];
			if (size_vector > size)
			{
				for (int i = 0; i < size; i++)
				{
					vector_vector[i] = vector[i];
					if (i == size - 1)
					{
						for (int j = 0; j < size_vector; j++)
						{
							vector_vector[j] = 0;
						}
					}
				}
			}
			if (size_vector < size)
			{
				for (int i = 0; i < size_vector; i++)
				{
					vector_vector[i] = vector[i];
				}
			}
			if (size_vector < 0)
			{
				throw "Новый размер массива меньше 0";
			}
			this->size = size_vector;
			delete[] vector;
			vector = vector_vector;
			std::cout << vector;
			vector_vector = nullptr;
		}
		if (size_vector < 0)
		{
			throw "Новый размер массива меньше 0";
		}
	}
	void resize(int size_vector, type buf)
	{
		if (size_vector >= 0)
		{
			type* vector_vector = new type[size_vector];
			if (size_vector > size)
			{
				for (int i = 0; i < size; i++)
				{
					vector_vector[i] = vector[i];
					if (i == size - 1)
					{
						for (int j = i; j < size_vector; j++)
						{
							vector_vector[j] = buf;
						}
					}
				}
			}
			if (size_vector < size)
			{
				for (int i = 0; i < size_vector; i++)
				{
					vector_vector[i] = vector[i];
				}
			}
			if (size_vector < 0)
			{
				throw "Новый размер массива меньше 0";
			}
			this->size = size_vector;
			delete[] vector;
			vector = vector_vector;
			vector_vector = nullptr;
		}

	}
	void output() {
		for (int i = 0; i < size; i++) {
			std::cout << vector[i] << " ";
		}
		std::cout << std::endl;
	}
	void empty() {
		if (size == 0) {
			std::cout << "Вектор пуст" << std::endl;
		}
		else std::cout << "Вектор имеет значения" << std::endl;
	}
	void push_back(int value) {
		double* vector1 = new double[size + 1];
		vector1[size] = value;
		for (int i = 0; i < size; i++) {
			vector1[i] = vector[i];
		}
		vector = vector1;
		size += 1;
	}
	void pop_back() {
		double* vector1 = new double[size - 1];
		for (int i = 0; i < size - 1; i++) {
			vector1[i] = vector[i];
		}
		vector = vector1;
		size -= 1;
	}

	void insert(double value) {
		double* vector1 = new double[size + 1];
		vector1[0] = value;

		for (int i = 1; i < size + 1; i++) {
			vector1[i] = vector[i - 1];
		}
		vector = vector1;
		size += 1;
	}

	void insert(int it, int n, double value) {
		size += n;
		double* vector1 = new double[size];

		for (int i = 0; i < size; i++) {
			if (i < it) {
				vector1[i] = vector[i];
			}
			else if ((i >= it) && (i < it + n)) {
				vector1[i] = value;
			}
			else {
				vector1[i] = vector[i - n];
			}
		}
		vector = vector1;
	}

	void front() {
		if (size != 0) {
			std::cout << "Значение первой ячейки " << vector[0] << std::endl;
		}
		else std::cout << "Вектор пуст" << std::endl;
	}

	void back() {
		if (size != 0) {
			std::cout << "Значение последней ячейки " << vector[size - 1] << std::endl;
		}
		else std::cout << "Вектор пуст " << std::endl;
	}

	void erase(int it) {
		size -= 1;
		double* vector1 = new double[size];

		for (int i = 0; i < size; i++) {
			if (i < it) {
				vector1[i] = vector[i];
			}
			else {
				vector1[i] = vector[i + 1];
			}
		}
		vector = vector1;
	}

	void clear() {
		delete[] vector;
		size = 0;
		vector = nullptr;
	}
	void swap1() //вставками
	{
		int counter = 0;
		for (int i = 1; i < size - 1; i++) {
			for (int j = i; j > 0 && vector[j - 1] > vector[j]; j--) {
				counter++;
				int tmp = vector[j - 1];
				vector[j - 1] = vector[j];
				vector[j] = tmp;
			}
		}
		std::cout << "Количество перестановок = " << counter << std::endl;
	}
	void Merge(Vector<type> vector) {
		int s = vector.getSize();
		if (s < 2) {
			return;
		}
		int mid = s / 2;
		Vector<type> left(mid);
		Vector<type> right(s - mid);
		for (int i = 0; i < mid;i++) {
			left[i] = vector[i];
		}
		for (int i = mid; i < s; i++) {
		     right[i-mid] = vector[i];
		}
		Merge(left);
		Merge(right);
		MergeSort(vector, left, right);
	}
	void MergeSort(Vector<type> vector, Vector<type> a, Vector<type> b) {
		int aminindex = 0;
		int bminindex = 0;
		int as = a.getSize();
		int bs = b.getSize();

		int targetVminindex = 0;
		while (aminindex < as && bminindex < bs) {
			if (a[aminindex] <= b[bminindex]) {
				vector[targetVminindex] = a[aminindex];
				aminindex++;
			}
			else {
				vector[targetVminindex] = b[bminindex];
				bminindex++;
			}
			targetVminindex++;
		}
		while (aminindex < as) {
			vector[targetVminindex] = a[aminindex];
			aminindex++;
			targetVminindex++;
		}
		while (bminindex < bs) {
			vector[targetVminindex] = b[bminindex];
			bminindex++;
			targetVminindex++;
		}
	}
		



	void input_size_ubivanie()
	{
		type* vector_vector = new type[size];

		for (int i = 0; i < size; i++)
		{
			vector_vector[i] = size - i;
		}
		delete[] vector;
		vector = vector_vector;
		vector_vector = nullptr;
	}
	void input_size_vozrastanie()
	{
		type* vector_vector = new type[size];

		for (int i = 0; i < size; i++)
		{
			vector_vector[i] = i;
		}
		delete[] vector;
		vector = vector_vector;
		vector_vector = nullptr;
	}
	void input_size_random()
	{
		type* vector_vector = new type[size];

		for (int i = 0; i < size; i++)
		{
			vector_vector[i] = rand() % 10000;
		}
		delete[] vector;
		vector = vector_vector;
		vector_vector = nullptr;
	}
	type& operator[](int index)
	{
		return vector[index];
	}
};




int main()
{
	float start_time, end_time;
	int index_first, index_second, size, buf, index;
	setlocale(LC_ALL, "rus");
	std::cout << "Введите размер массива" << std::endl;
	std::cin >> size;
	Vector<int> vector_one(size);
	std::cout << "\n-----" << std::endl;
	
	//-----------—
	std::cout << "СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ ВСТАВКАМИ" << std::endl;
	vector_one.input_size_vozrastanie();
	start_time = clock();
	vector_one.swap1();
	end_time = clock();

	std::cout << std::endl;
	std::cout << "Время выполнения = " << (end_time - start_time) / CLOCKS_PER_SEC << "\n\n" << std::endl;
	std::cout << "СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ ГНОМЬЯ" << std::endl;
	vector_one.input_size_vozrastanie();
	start_time = clock();
	vector_one.Merge(vector_one);
	end_time = clock();

	std::cout << std::endl;
	std::cout << "Время выполнения = " << (end_time - start_time) / CLOCKS_PER_SEC << "\n\n" << std::endl;

	std::cout << "СОРТИРОВКА МАССИВА ПО УБЫВАНИЮ ВСТАВКАМИ" << std::endl;
	vector_one.input_size_ubivanie();
	start_time = clock();
	vector_one.swap1();
	end_time = clock();

	std::cout << std::endl;
	std::cout << "Время выполнения = " << (end_time - start_time) / CLOCKS_PER_SEC << "\n\n" << std::endl;
	std::cout << "СОРТИРОВКА МАССИВА ПО УБЫВАНИЮ ГНОМЬЯ" << std::endl;
	vector_one.input_size_ubivanie();
	start_time = clock();
	vector_one.Merge(vector_one);
	end_time = clock();

	std::cout << std::endl;
	std::cout << "Время выполнения = " << (end_time - start_time) / CLOCKS_PER_SEC << "\n\n" << std::endl;

	std::cout << "СОРТИРОВКА МАССИВА СЛУЧАЙНЫХ ЗНАЧЕНИЙ ПУЗЫРЬКОМ" << std::endl;
	vector_one.input_size_random();
	vector_one.output();
	start_time = clock();
	vector_one.swap1();
	vector_one.output();
	end_time = clock();

	std::cout << std::endl;
	std::cout << "Время выполнения = " << (end_time - start_time) / CLOCKS_PER_SEC << "\n\n" << std::endl;
	std::cout << "СОРТИРОВКА МАССИВА СЛУЧАЙНЫХ ЗНАЧЕНИЙ ГНОМЬЯ" << std::endl;
	vector_one.input_size_random();
	vector_one.output();
	start_time = clock();
	vector_one.Merge(vector_one);
	end_time = clock();
	vector_one.output();

	std::cout << "Время выполнения = " << (end_time - start_time) / CLOCKS_PER_SEC << "\n\n" << std::endl;


	return 0;
}