/*--------------------------------------------------------------------------------------
	Дано натуральное число N (1<=N<=100), целочисленный линейный массив a0, a1, …, aN-1.
Элементы массива заполняются случайными целыми числами из диапазона [0, N]. Требуется 
отсортировать массив используя алгоритм сортировки выбором. После сортировки 
произвести поиск в массиве введенного значения при помощи алгоритма последовательного 
поиска с барьером в начале массива.
----------------------------------------------------------------------------------------
									Выполнил: Анисимов Никита Сергеевич, ИТ-11*/
#include <iostream>
#include <time.h>
using namespace std;

void random_array (int max_numb, int array_x[]);
void insertion_sort (int numb_of_array_el, int array_x[]);
void search_in_array (int length_array, int elements, int array_x[]);
void print_array (int max_numb, int array_x[]);

int main () 
{
	setlocale(0,"Rus");
	int N,K;
	cout<<"Введите число, которое будет являться размером массива и  максимальным элементом в этом массиве одновременно"<<endl;
	cin>>N;
	int *p=new int[N];
	random_array(N,p);//заполняем массив 
	print_array(N,p);
	insertion_sort(N,p);//сортируем массив
	print_array(N,p);
	cout<<"Введите число для его поиска в массиве"<<endl;
	cin>>K;
	search_in_array(N,K,p);//ищем K в массиве
	delete[]p;
	system("pause");
	return 0;
}

/*--------------------------------------------------------------------------------------
	Функция заполняет входной массив целочисленными случайными числами из диапазона 
от 0 до входного параметра.
----------------------------------------------------------------------------------------*/
void random_array (int max_numb, int array_x[])
{
	srand(time(NULL));//параметр, благодаря которому генерируются действительно случайные числа
	int i;
	for (i=0;i<max_numb;i++)
		array_x[i]=rand()%max_numb;
	return;
}

/*--------------------------------------------------------------------------------------
	Функция выводит на экран входной массив.
----------------------------------------------------------------------------------------*/
void print_array (int max_numb, int array_x[])
{
	int i;
	for (i=0;i<max_numb;i++)
		cout<<array_x[i]<<" ";
	cout<<endl;
	return;
}
/*--------------------------------------------------------------------------------------
	Функция реализует алгоритм сортировки выбором над входным массивом.
----------------------------------------------------------------------------------------*/
void insertion_sort (int numb_of_array_el, int array_x[])
{
	int i,j,min;//min-текущее минимальное значение в массиве
	int index_min;
	for (j=0;j<numb_of_array_el;j++)
	{
		min=array_x[j];
		index_min=j;
		for (i=j;i<numb_of_array_el;i++)
		{
			if (array_x[i]<min)
			{
				min=array_x[i];
				index_min=i;
			}
		}
		array_x[index_min]=array_x[j];
		array_x[j]=min;
	}
	return;
}

/*--------------------------------------------------------------------------------------
	Функция реализует поиск входного элемента во входном массиве алгоритмом 
последовательного поиска с барьером в начале массива. 
----------------------------------------------------------------------------------------*/
void search_in_array (int length_array, int elements, int array_x[])
{
	int i;
	int *q=new int[length_array+1];//Создаём новый массив размерностью на 1 больше исходного
	for (i=0;i<length_array;i++)
		q[i]=array_x[i];		   //и заполняем его теми же элементами
	q[length_array]=elements;	   //кроме последнего элемента, который будет выполнять функцию барьера
	i=0;
	while (q[i]!=elements)
		i++;
	if(i!=length_array)
		cout<<i+1<<"ый элемент массива является искомым числом"<<endl;
	else
		cout<<"этого элемента нет в массиве"<<endl;
	return;
}