#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <ctime>

using namespace std;

const int N = 100000; //Розмер массива
ofstream file_out("output.txt"); //Открытие файла для записи.

void copy_array(int arr1[N], int arr2[N]); //Функция для копирования массива
void bublesort(int arr[N]); //Функция для алгоритма быстрой сортировки
void InsertSort(int arr[N]); //Функция для алгоритма сортировки вставками
void QuickSort(int arr[N], int m, int n); //Функция для алгоритма быстрой сортировки

int main()
{
    setlocale(LC_ALL, "rus");
    srand(time(NULL));
    int arr[N]; //Исходный массив
    int rand_array[N]; //Рандомный массив

    for (int i = 0; i < N; i++)
        rand_array[i] = rand() % 10000 - 5000; //Генерация массива

    copy_array(arr, rand_array); //Копируем массив

    file_out << "array: ";
    for (int i = 0; i < N; i++)
        file_out << arr[i] << " "; //Вывод сгенерированного массива в файл
    file_out << "\n\n\n";

    bublesort(arr); //Сортировка пузырьком
    system("PAUSE"); //Пауза

    copy_array(arr, rand_array); //Копируем массив

    InsertSort(arr); //Сортировка вставками
    system("PAUSE"); //Пауза

    copy_array(arr, rand_array); //Копируем массив

    cout << "Идет быстрая сортировка..... " << '\n'; //Начало быстрой сортировки
    double time_start = clock(); //Включаем секундомер
    QuickSort(arr, 0, N); //Быстрая сортировка
    double time_finish = clock(); //Выключаем секундомер
    file_out << "\n\nQuick Sort: ";
    for (int i = 0; i < N; i++)
        file_out << arr[i] << ' '; //Вывод отсоотированого массива

    double time_insert_sort = (time_finish - time_start) / 1000; //Время работы сортировки
    printf("Время сортировки: %.2f\n", time_insert_sort); //Вывод времени
    system("PAUSE"); //Пауза
    return 0;
}

void bublesort(int arr[N])
{
    cout << "Идет сотировка 'Пузырьком'..... " << '\n'; //Начало сортировки
    double time_start = clock(); //Включаем секундомер
    for (int i = 0; i < N - 1; i++) //Цыкл обхода
    {
        for (int j = 0; j < N - i - 1; j++)
        {
            if (arr[j] < arr[j + 1]) //Если правый больше левого меняем
            {
                int dump = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = dump;
            }
        }
    }
    double time_finish = clock(); //Выключаем секундомер

    file_out << "Buble sort: ";
    for (int i = 0; i < N; i++)
        file_out << arr[i] << ' '; //Вывод отсортированого массива

    double time_buble_sort = (time_finish - time_start) / 1000; //Время работы алгоритма
    printf("Время сортировки: %.2f\n", time_buble_sort); //Вывод времени работы
}

void InsertSort(int arr[N])
{
    cout << "Идет сотировка вставками..... " << '\n'; //Начало сортировки
    double time_start = clock(); //Включаем секундомер

    for (int i = 1; i < N; i++)
    {
        int key = arr[i]; //Ставим ключ
        int j = i - 1; //До ключа
        while (j >= 0 && arr[j] > key) //Если елемент до ключа больше ключа
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j + 1] = key; //Ставим значение ключа на новое место
    }

    double time_finish = clock(); //Выключаем секундомер
    file_out << "\n\nInserting sort: ";
    for (int i = 0; i < N; i++)
        file_out << arr[i] << ' '; //Выводи массив

    double time_insert_sort = (time_finish - time_start) / 1000; //Время работы алгоритма
    printf("Время сортировки: %.2f\n", time_insert_sort); //Выводим время работы
}

void QuickSort(int arr[N], int m, int n)
{
    int i = 0, j = n - 1; //Ставим значения
    int temp, p; //Переменная для хранения и середина массива

    p = arr[n / 2]; //Значение середины

    do {
        while (arr[i] < p) i++; //Ищем неправильные елементы
        while (arr[j] > p) j--;

        if (j >= i) //Меняем местами два этих элемента
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; //продвигаем ключи
            j--;
        }
    } while (i <= j); //Пока ключ конца больше или равен ключу начала

    if (i < n) QuickSort(arr, i, n-i); //Если есть что сортировать рекурсивно вызываем функцию
    if (j > 0) QuickSort(arr, 0, j);
}

void copy_array(int arr1[N], int arr2[N])
{
    for (int i = 0; i < N; i++)
        arr1[i] = arr2[i]; //Копируем массивы
}