//! @file
//! \brief Программа перевода числовой записи времени в текстово-числовую форму записи
//! @mainpage
//-----------------------------------------------------------------------------------------------------------------
//! \author     Ветошкин Артем
//! \version    alpha 1
//! \date       03.09.2019
//! \mail       vet_v2002@mail.ru
//=================================================================================================================

#define _USE_MATH_DEFINES

#include <iostream>
#include <assert.h>
#include <math.h>
#include <time.h>

int cmpDecr(int p1, int p2)
{
    if (p1 > p2)
        return -1;
    if (p1 < p2)
        return 1;
    return 0;
}

int cmpIncr(int p1, int p2)
{
    if (p1 > p2)
        return 1;
    if (p1 < p2)
        return -1;
    return 0;
}

//-----------------------------------------------------------------------------------------------------------------
//! \brief   Сортировка выбором максимального
//!
//! \param      left            начало сортируемого участка
//! \param      right           конец сортируемого участка включительно
//! \param[out] swaping         число обменов
//! \param[out] comparisons     число сравнений
//! \param[out] Array           сортеруемый массив
//!
//------------------------------------------------------------------------------------------------------------------

void selectionSorting(int left, int right, int* swaping, int* comparisons, int* Array, int (*cmp)(int a, int b) = cmpIncr)
{
    assert(swaping      != nullptr);
    assert(comparisons  != nullptr);
    assert(swaping      != comparisons);
    assert(Array        != nullptr);
    assert(cmp          != nullptr);

    for (int i = right-1; i >= left; --i)
    {
        int max   = Array[i];
        int index = i;

        for (int j = i - 1; j >= left; --j)
        {
            if (cmp(Array[j], max) == 1)
            {
                max = Array[j];
                index = j;

                (*swaping)++;
            }

            (*comparisons)++;
        }

        if (Array[i] != Array[index])
        {
            std::swap(Array[i], Array[index]);
            (*swaping)++;
        }
        (*comparisons)++;
    }
}

//-----------------------------------------------------------------------------------------------------------------
//! \brief   Сортировка пузырьком
//!
//! \param      left            начало сортируемого участка
//! \param      right           конец сортируемого участка включительно
//! \param[out] swaping         число обменов
//! \param[out] comparisons     число сравнений
//! \param[out] Array           сортеруемый массив
//!
//-----------------------------------------------------------------------------------------------------------------

void bubbleSorting(int left, int right, int* swaping, int* comparisons, int* Array, int (*cmp)(int a, int b) = cmpIncr)
{
    assert(swaping      != nullptr);
    assert(comparisons  != nullptr);
    assert(swaping      != comparisons);
    assert(Array        != nullptr);
    assert(cmp          != nullptr);

    bool end = false;

    while (!end)
    {
        end = true;

        for (int i = left + 1; i < right; i++)
        {
            if (cmp(Array[i - 1], Array[i]) == 1)
            {
                std::swap(Array[i], Array[i - 1]);
                (*swaping)++;

                end = false;
            }

            (*comparisons)++;
        }

        right--;
    }
}

void fillRandInt(int* Array, size_t size, int left, int right)
{
    for (size_t i = 0; i < size; i++)
    {
        Array[i] = left + (right - left + 1) * rand() / RAND_MAX;
    }
}

void copyNElments(int* ArrayFrom, int* ArrayTo, size_t size)
{
    for (size_t i = 0; i < size; i++)
    {
        ArrayTo[i] = ArrayFrom[i];
    }
}

void printArray(int* Array, size_t size)
{
    printf("Array: ");
    for (size_t i = 0; i < size; i++)
        printf("%d ", Array[i]);
}

void FirstTask()
{
    int Array[6];
    int Array2[6];

    int swaping = 0, comparisons = 0;

    fillRandInt(Array, 6, 1, 100);
    copyNElments(Array, Array2, 6);

    printArray(Array, 6);
    printf("\nСортировка пузырьком: \n");

    bubbleSorting(0, 6, &swaping, &comparisons, Array);

    printArray(Array, 6);
    printf(" обменов: %4d сравнений: %4d \n", swaping, comparisons);

    swaping = 0, comparisons = 0;
    bubbleSorting(0, 6, &swaping, &comparisons, Array);

    printArray(Array, 6);
    printf(" обменов: %4d сравнений: %4d \n", swaping, comparisons);

    swaping = 0, comparisons = 0;
    bubbleSorting(0, 6, &swaping, &comparisons, Array, cmpDecr);

    printArray(Array, 6);
    printf(" обменов: %4d сравнений: %4d \n", swaping, comparisons);

    printf("Сортировка вставкой: \n");

    selectionSorting(0, 6, &swaping, &comparisons, Array2);

    printArray(Array2, 6);
    printf(" обменов: %4d сравнений: %4d \n", swaping, comparisons);

    swaping = 0, comparisons = 0;
    selectionSorting(0, 6, &swaping, &comparisons, Array2);

    printArray(Array2, 6);
    printf(" обменов: %4d сравнений: %4d \n", swaping, comparisons);

    swaping = 0, comparisons = 0;
    selectionSorting(0, 6, &swaping, &comparisons, Array2, cmpDecr);

    printArray(Array2, 6);
    printf(" обменов: %4d сравнений: %4d \n", swaping, comparisons);
}

int main()
{
    srand(time(0));

    setlocale(LC_ALL, "Rus");


    FirstTask();

    int a;
    std::cin >> a;

    int    step        = 10;
    size_t size        = 100;
    int    swaping     = 0;
    int    comparisons = 0;

    int *Array        = new int[size];
    int *SortingArray = new int[size];

    fillRandInt(Array,        size, 0, 1000);
    fillRandInt(SortingArray, size, 0, 1000);

    printf("+------------+---------------------------------------------+--------------------------------------------+\n");
    printf("|            |            Сортировка пузырьком             |           Сортировка вставкой              |\n");
    printf("|   Размер   +----------------------+----------------------+---------------------+----------------------+\n");
    printf("|            |       Сравнений      |        Обменов       |      Сравнений      |         Обменов      |\n");
    printf("+------------+----------------------+----------------------+---------------------+----------------------+\n");

    for (size_t i = 0; i <= size; i += step)
    {
        copyNElments(Array, SortingArray, i);

        swaping = 0, comparisons = 0;
        bubbleSorting(0, i - 1, &swaping, &comparisons, SortingArray);

        printf("| %10d | %20d | %20d |", i, comparisons, swaping);

        copyNElments(Array, SortingArray, i);

        swaping = 0, comparisons = 0;
        selectionSorting(0, i - 1, &swaping, &comparisons, SortingArray);

        printf("%20d | %20d |\n", comparisons, swaping);

        printf("+------------+----------------------+----------------------+---------------------+----------------------+\n");
    }


    system("pause");
}