/*24.11.2014 - Лабораторная работа #4. Калинина Екатерина (ФИТ-1). Вариант 11.
1. удалить элементы, совпадающие с минимальным +
2. добавить N после всех четных элементов +
3. поменять местами элементы с четными и нечетными номерами +
4. найти элемент с заданным ключом (значением) +
5. выполнить сортировку простым выбором по возрастанию +
6. найти элемент с заданным ключом (значением) -(?) */

#include <iostream>
#include <fstream>
#include <locale.h>

using namespace std;

void readFile(int *mas, int n)
/*функция чтения массива из файла и вывода его на экран*/
{
	ifstream input("input.txt", ios::in);
	for (int i = 0; i<n; i++)
	{
		input >> mas[i];
		cout << mas[i] << " ";
	}
	cout << "\n";
}
void writeFile(int *mas, int n)
/*функция записи массива в файл*/
{
	ofstream output("output.txt", ios::app);
	for (int i = 0; i<n; i++) output << mas[i] << " ";
	output << "\n";
	output.close();
}
void delete_min(int *mas, int n)
/*функция удаления минимальных элементов*/
{
	int min, i, j, k = 0; //k-количество чисел, равных минимальному
	min = mas[0];
	for (i = 1; i<n; i++) //нахождение минимального элемента массива
	if (mas[i]<min) min = mas[i];
	for (i = 0; i<n; i++)
	if (mas[i] == min)
	{
		k++;
		for (j = i; j<(n - 1); j++) mas[j] = mas[j + 1];
	}
	n = n - k;
	for (i = 0; i<n; i++) cout << mas[i] << " ";
	cout << "\n";
	writeFile(mas, n);
}
void add_n(int *mas, int &n, int k)
/*функция вставки N(изначальная размерность массива) после четных элементов*/
{
	int i, j;
	for (i = -1; i<(n - 1); i++)
	{
		if ((mas[i] % 2) == 0)
		{
			n++;
			for (j = (n - 1); j>i; j--)
				mas[j] = mas[j - 1];
			mas[i + 1] = k; // вставка нового элемента
			i++; // обход нового элемента
		}
	}
	n--;
	for (i = 0; i<n; i++) cout << mas[i] << " ";
	cout << "\n";
	writeFile(mas, n);
	return;
}
void change(int *mas, int n)
/*функция перестановки местами соседних элементов (с четными и нечетными номерами)*/
{
	int a = 0;
	for (int i = 0; i<(n - 1); i += 2)
	{
		a = mas[i];
		mas[i] = mas[i + 1];
		mas[i + 1] = a;
	}
	for (int i = 0; i<n; i++) cout << mas[i] << " ";
	cout << "\n";
	writeFile(mas, n);
}
void linearSearch(int *mas, int n)
/*функция поиска в неотсортированном массиве (линейный поиск)*/
{
	ofstream output("output.txt", ios::app);
	int key, i = 0, s = 0;
	bool k = false;
	cout << "Введите ключ \n";
	cin >> key;
	//while (k==false)
	while ((k == false) && (i<n))
	{
		if (mas[i] == key)k = true;
		i++;
		s++;
	}
	if (k)
	{
		cout << "Элемент " << key << " найден под номером " << i << "\n";
		output << "Элемент " << key << " найден под номером " << i << "\n";
	}
	else
	{
		cout << "Элемент " << key << " не найден. \n";
		output << "Элемент " << key << " не найден. \n";
	}
	cout << "Для поиска использовали " << s << " сравнений. \n";
	output << "Для поиска использовали " << s << " сравнений. \n";
}
void sort(int *mas, int n)
/*функция сортировки массива методом простого выбора по возрастанию*/
{
	int min, imin;
	for (int i = 0; i<n; i++)
	{
		min = mas[i];
		imin = i;
		for (int j = i + 1; j<n; j++)  //поиск минимального элемента массива
		if (mas[j]<min)
		{
			min = mas[j];
			imin = j;
		}
		mas[imin] = mas[i]; //меняем местами минимальный с первым неотсортированным
		mas[i] = min;
	}
	for (int i = 0; i<n; i++) cout << mas[i] << " ";
	cout << "\n";
	writeFile(mas, n);
	return;
}
void binarySearch(int *mas, int n)
/*функция поиска в отсортированном массиве (бинарный поиск)*/
{
	ofstream output("output.txt", ios::app);
	int key, left = 0, right = n, middle, s = 0;
	cout << "Введите ключ \n";
	cin >> key;
	while (left <= right)
	{
		s++;
		middle = (left + right) / 2; //средний элемент
		if (mas[middle]<key) left = middle + 1; //перенести левую границу
		else if (mas[middle] == key)
		{
			cout << "Элемент " << key << " найден под номером " << middle + 1 << "\n";
			output << "Элемент " << key << " найден под номером " << middle + 1 << "\n";
			break;
		}
		else right = middle - 1;
		middle = (left + right) / 2;
	}
	//if (left>right)
	//{
	//	cout << "Элемент " << key << " не найден. \n";
	//	output << "Элемент " << key << " не найден. \n";
	//}
	cout << "Для поиска использовали " << s << " сравнений. \n";
	output << "Для поиска использовали " << s << " сравнений. \n";
	output.close();
}
void main()
{
	setlocale(LC_ALL, "rus");
	ifstream A("input.txt", ios::in);
	ofstream B("output.txt", ios::out);
	int n;
	cout << "Введите размерность массива: \n";
	cin >> n;
	int K = n;
	int *massive = new int[n]; // выделение динамической памяти под массив из n элементов
	A.close();
	cout << "Исходный массив: \n";
	readFile(massive, n);
	writeFile(massive, n);
	cout << "Удаление минимальных: \n";
	delete_min(massive, n);
	cout << "Добавление N после чётных: \n";
	add_n(massive, n, K);
	cout << "Перестановка соседних элементов: \n";
	change(massive, n);
	cout << "Поиск в неотсортированном массиве: \n";
	linearSearch(massive, n);
	cout << "Сортировка простым выбором (по возрастанию): \n";
	sort(massive, n);
	cout << "Поиск в отсортированном массиве: \n";
	binarySearch(massive, n);

}