// Подключение библиотек
#include <iostream> // Библиотека для реализации ввода-вывода
#include <vector>   // Библиотека для работы с векторами
#include <string>   // Библиотека для работы со строками
#include <fstream>  // Библиотека для работы с файлами
#include <ctime>    // Для работы со временем
#include <iterator> // Заголовочный файл итераторов
#include <algorithm>// Тестим стандартную функцию sort

// Используем стандартное пространство имен
using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Простой обмен (пузырек)
// Каждый элемент попарно сравнивается с предыдущим
// Если предыдущий элемент больше текущего, то они меняются местами
// Таким образом происходит смещение минимумов в начало массива
// Повторяем выше изложенные действия для всех элементов, кроме первого (n-1-i) и т.д.
void bubble(double *mas, int n)
{
    double t=0;                        // t - для временного хранения элемента массива
    for(int i=n-1; i>=0; i--)          // i - номер текущего прохода массива.
    {                                  // Изменяется от n-1 (последнего элемента) до первого элемента
        for(int j=n-1; j>(n-1-i); j--) // j - номер элемента. После каждого прохода кол-во элементов сокращается на 1
                                       // так как после каждой итерации в начале будут появляться минимумы
        {
            if (mas[j-1] > mas[j])     // Если предыдущий элемент больше текущего, то они меняются местами
            {
                t=mas[j];
                mas[j] = mas[j-1];
                mas[j-1] = t;
            }
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Простой обмен для вектора
void bubble_vector(vector<double> &myVector)
{
    double t=0;
    for(int i=myVector.size()-1; i>=0; i--)
    {
        for(int j=myVector.size()-1; j>(myVector.size()-1-i); j--)

        {
            if (myVector[j-1] > myVector[j])
            {
                t=myVector[j];
                myVector[j] = myVector[j-1];
                myVector[j-1] = t;
            }
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Простой выбор
// 1. Организуем поиск минимума в массиве
// 2. Меняем местами первый элемент и минимум
// 3. Повторяем алгоритм для элементов, исключая первый
void simple_choice(double *mas, int n) // В качестве аргументов указатель на массив и его размер
{
    double min;                        // Хранит минимум
    int index = 0;                     // Хранит индекс минимума
    for(int i=0; i<(n-1); i++)             // Обходим все элементы
    {
        min = mas[i];
        index=i;
        for(int j=i+1; j<n; j++)         // Ищим минимум
        {
            if (min > mas[j])
            {
                min = mas[j];          // Запоминаем минимум и его индекс
                index = j;
            }
        }

        mas[index] = mas[i];           // Меняем местами минимум и элемент с индексом i.
        mas[i] = min;
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Простой выбор для вектора
void simple_choice_vector(vector<double> &myVector)
{
    double min;
    int index = 0;
    for(int i=0; i<(myVector.size()-1); i++)
    {
        min = myVector[i];
        index = i;
        for(int j=i+1; j<myVector.size(); j++)
        {
            if (min > myVector[j])
            {
                min = myVector[j];
                index = j;
            }
        }

        myVector[index] = myVector[i];
        myVector[i] = min;
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Простое включение
// Начиная со второго элемента, сравниваем все предыдущие элементы с текущим.
// В случае, если предыдущий элемент оказался большим, меняем местами текущий и предыдущий
void simple_including(double *mas, int n)
{
    // Переменная для временного хранения элементов массива
    double t = 0;
    // Начиная со второго элемента
    for(int i=1; i<n; i++)
    {
        // Проверяем все предыдущие элементы
        for(int j=0; j<i; j++)
        {
            // Если один из предыдущих больше текущего, меняем местами
            if (mas[j] > mas[i])
            {
                t = mas[j];
                mas[j] = mas[i];
                mas[i] = t;
            }
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Простое включение для вектора
void simple_including_vector(vector<double> &myVector)
{
    double t = 0;
    for(int i=1; i<myVector.size(); i++)
    {
        for(int j=0; j<i; j++)
        {
            if (myVector[j] > myVector[i])
            {
                t = myVector[j];
                myVector[j] = myVector[i];
                myVector[i] = t;
            }
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Вывод вектора на экран
// Вывод производится в цикле
void show_vector(vector<double> &myVector)
{
    cout<<endl<<"The vector: "<<endl;
    for(int i=0; i<myVector.size(); i++)
    {
        cout<<myVector[i]<<" ";
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Альтернативная реализация вывода вектора на экран (используя итераторы)
void show_vector_alt(vector<double> &myVector)
{
    copy(myVector.begin(),  // Итератор начала массива
         myVector.end(),    // Итератор конца массива
         ostream_iterator<double>(cout, " "));
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Функция для вывода массива на экран
void show_massive(double *mas, int n)
{
    cout<<endl<<"The array: "<<endl;
    for(int i=0; i<n; i++)
    {
        cout<<mas[i]<<" ";
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Функция для заполнения вектора случайными числами
void fill_vector(vector<double> &myVector)
{
    srand(time(NULL)); // Для того, чтобы при повторном запуске программы выводились другие числа
    for(int i=0; i<myVector.size(); i++)
    {
        myVector[i] = rand()%10000;
    }
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Функция для заполнения масива случайными числами
void fill_massive(double *mas, int n)
{
    srand(time(NULL));
    for(int i=0; i<n; i++)
    {
        mas[i] = rand()%10000;
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Функция для организации ввода элементов массива с клавиатуры
void enter_massive(double *mas, int n)
{
    cout<<endl<<"Enter "<<n<<" elements in the array:"<<endl;
    for(int i=0; i<n; i++)
    {
        cin>>mas[i];
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Производим сортировку всеми методами. Результаты сравниваем
void compare(vector<double> &myVector, double *mas, int n)
{
    clock_t start;   // Количество временных тактов до запуска алгоритма сортировки
    clock_t stop;    // Количество временных тактов после запуска алгоритма
    cout<<endl<<"Comparison for array:"<<endl;

    fill_massive(mas, n); // Каждый раз заново заполняем массив для более объективной оценки
    start = clock(); // Запоминаем кол-во временных тактов
    bubble(mas, n);
    stop = clock();  // Запоминаем новое кол-во временных тактов
    cout<<endl<<"THE BUBBLE SORT. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";

    fill_massive(mas, n);
    start = clock();
    simple_choice(mas, n);
    stop = clock();  // Запоминаем новое кол-во временных тактов
    cout<<endl<<"THE SIMPLE CHOICE. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";

    fill_massive(mas, n);
    start = clock();
    simple_including(mas, n);
    stop = clock();  // Запоминаем новое кол-во временных тактов
    cout<<endl<<"THE SIMPLE INCLUDING. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";
    start = clock();
    sort(mas, mas + n);
    stop = clock();
    cout<<endl<<"SORT. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";

    cout<<endl<<endl<<"Comparison for vector:"<<endl;
    fill_vector(myVector);
    start = clock();
    simple_choice_vector(myVector);
    stop = clock();  // Запоминаем новое кол-во временных тактов
    cout<<endl<<"THE SIMPLE CHOICE. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";

    fill_vector(myVector); // Каждый раз заново заполняем массив для более объективной оценки
    start = clock(); // Запоминаем кол-во временных тактов
    bubble_vector(myVector);
    stop = clock();  // Запоминаем новое кол-во временных тактов
    cout<<endl<<"THE BUBBLE SORT. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";

    fill_vector(myVector);
    start = clock();
    simple_including_vector(myVector);
    stop = clock();  // Запоминаем новое кол-во временных тактов
    cout<<endl<<"THE SIMPLE INCLUDING. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";
    start = clock();
    sort(myVector.begin(), myVector.end());
    stop = clock();
    cout<<endl<<"SORT. Time of sorting: "
        <<double(stop-start) / CLOCKS_PER_SEC<<" seconds";
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Считывание массива из файла
void read_from_file(const string filename, double *mas)
{   int n=0; // Количество элементов
    fstream fi;
    fi.open(filename, ios::in);
    fi>>n;
    for(int i=0; i<n; i++)
    {
        fi >> mas[i];
    }
}