// L1.cpp: определяет точку входа для консольного приложения.
// ConsoleApplication1.cpp: определяет точку входа для консольного приложения.

#include "stdafx.h"
#include <cstdlib>
#include <iostream>


using namespace std;

void Fill_mas(int * a)
{
    for (int i = 0; i < 10; i++)// Задаем значения элементов массива
        a[i] = rand() % 100;
}

void Mas_out(int *a)
{
    for (int i = 0; i < 10; i++)// Выводим значения неотсортированных элементов массива
        cout << a[i] << " ";
    cout << endl;
}

void Sort1(int *num, int size)
{
    //Сортировка пузырьком
    // Для всех элементов
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = (size - 1); j > i; j--) // для всех элементов после i-ого
        {
            if (num[j - 1] > num[j]) // если текущий элемент меньше предыдущего
            {
                int temp = num[j - 1];
                num[j - 1] = num[j];
                num[j] = temp;
            }
        }
    }
    for (int i = 0; i < 10; i++)
        cout << num[i] << " ";
    cout << endl;
}

void Sort2(int *arrayPtr, int length) // сортировка вставками
{
    int temp, // временная переменная для хранения значения элемента сортируемого массива
        item; // индекс предыдущего элемента
    for (int counter = 1; counter < length; counter++)
    {
        temp = arrayPtr[counter]; // инициализируем временную переменную текущим значением элемента массива
        item = counter - 1; // запоминаем индекс предыдущего элемента массива
        while (item >= 0 && arrayPtr[item] > temp) // пока индекс не равен 0 и предыдущий элемент массива больше текущего
        {
            arrayPtr[item + 1] = arrayPtr[item]; // перестановка элементов массива
            arrayPtr[item] = temp;
            item--;
        }
    }
    for (int i = 0; i < 10; i++)
        cout << arrayPtr[i] << " ";
    cout << endl;
}

void Sort3(int* array_Ptr, int length_array) // сортировка выбором
{
    for (int repeat_counter = 0; repeat_counter < length_array; repeat_counter++)
    {
        int temp = array_Ptr[0]; // временная переменная для хранения значения перестановки
        for (int element_counter = repeat_counter + 1; element_counter < length_array; element_counter++)
        {
            if (array_Ptr[repeat_counter] > array_Ptr[element_counter])
            {
                temp = array_Ptr[repeat_counter];
                array_Ptr[repeat_counter] = array_Ptr[element_counter];
                array_Ptr[element_counter] = temp;
            }
        }
    }
    for (int i = 0; i < 10; i++)
        cout << array_Ptr[i] << " ";
    cout << endl;
}

void Sort4(int *mas, int first, int last)
{
    int mid, count;
    int f = first, l = last;
    mid = mas[(f + l) / 2]; //вычисление опорного элемента
    do
    {
        while (mas[f] < mid) f++;
        while (mas[l] > mid) l--;
        if (f <= l) //перестановка элементов
        {
            count = mas[f];
            mas[f] = mas[l];
            mas[l] = count;
            f++;
            l--;
        }
    } while (f < l);

    if (first < l) {
        Sort4(mas, first, l);
    }
    if (f < last) {
        Sort4(mas, f, last);
    }
}

void Sort5(int *A, int first, int last)
{
    int middle, start, final, j;
    int *mas = new int[100];
    middle = (first + last) / 2; //вычисление среднего элемента
    start = first; //начало левой части
    final = middle + 1; //начало правой части
    for (j = first; j <= last; j++) //выполнять от начала до конца
        if ((start <= middle) && ((final>last) || (A[start]<A[final])))
        {
            mas[j] = A[start];
            start++;
        }
        else
        {
            mas[j] = A[final];
            final++;
        }
    //возвращение результата в список
    for (j = first; j <= last; j++) A[j] = mas[j];
    delete[]mas;


};

void Sort5_1(int *A, int first, int last) //рекурсивная процедура сортировки
{
    {
        if (first<last)
        {
            Sort5_1(A, first, (first + last) / 2); //сортировка левой части
            Sort5_1(A, (first + last) / 2 + 1, last); //сортировка правой части
            Sort5(A, first, last); //слияние двух частей
        }
    }

}


int main()
{
    int a[10]; // Объявляем массив из 10 элементов

    Fill_mas(a);

    Mas_out(a);

    Sort1(a, 10);  // вызываем функцию сортировки пузырьком
    Fill_mas(a);

    Sort2(a, 10); // вызываем функцию сортировки вставками
    Fill_mas(a);

    Sort3(a, 10);  // вызываем функцию сортировки выбором
    Fill_mas(a);

    Sort4(a, 0, 9);  // вызываем функцию быстрой сортировки
    Mas_out(a);
    Fill_mas(a);

    Sort5_1(a, 0, 9);  // вызываем функцию сортировки слияниями
    Mas_out(a);
    Fill_mas(a);

    system("pause");

    return 0;
}