#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::swap;
using std::vector;

const size_t kSpacingSize = 36;
const size_t kFirstSize = 100;
const size_t kSecondSize = 1000;
const int kLeftNumRange = 0;
const int kRightNumRange = 1000;

void quick_sort(vector<int>& _Container, int _Left, int _Right, size_t& _Iterations, size_t& _Compares)
{
    _Iterations++;
    int i = _Left, j = _Right;

    int tmp;

    int pivot = _Container[(_Left + _Right) / 2];

    _Compares++;
    while (i <= j)
    {
        _Compares++;
        while (_Container[i] < pivot)
        {
            i++;
            _Compares++;
        }
        _Compares++;
        while (_Container[j] > pivot)
        {
            j--;
            _Compares++;
        }

        _Compares++;
        if (i <= j)
        {
            tmp = _Container[i];
            _Container[i] = _Container[j];
            _Container[j] = tmp;
            i++;
            j--;
        }
    };
    _Compares++;
    if (_Left < j)
        quick_sort(_Container, _Left, j, _Iterations, _Compares);

    _Compares++;
    if (i < _Right)
        quick_sort(_Container, i, _Right, _Iterations, _Compares);
}

void heap_method(vector<int>& _Container, const size_t& _Size, const size_t& _Pos, size_t& _Iterations,
    size_t& _Compares)
{
    _Iterations++;
    size_t largest = _Pos;
    const size_t left = 2 * _Pos + 1;
    const size_t right = 2 * _Pos + 2;

    if (left < _Size && _Container[left] > _Container[largest])
    {
        largest = left;
        _Compares++;
    }
    if (right < _Size && _Container[right] > _Container[largest])
    {
        largest = right;
        _Compares++;
    }
    if (largest != _Pos)
    {
        swap(_Container[_Pos], _Container[largest]);
        _Compares++;
        heap_method(_Container, _Size, largest, _Iterations, _Compares);
    }
}

void heap_sort(vector<int>& _Container, const size_t& _Size, size_t& _Iterations, size_t& _Compares)
{
    for (int i = static_cast<int>(_Size) / 2 - 1; i >= 0; i--)
    {
        heap_method(_Container, _Size, i, _Iterations, _Compares);
    }
    for (int i = static_cast<int>(_Size) - 1; i >= 0; i--)
    {
        swap(_Container[0], _Container[i]);

        heap_method(_Container, i, 0, _Iterations, _Compares);
    }
}

void bubble_sort(vector<int>& _Container, size_t& _Iterations, size_t& _Compares)
{
    for (size_t i = 0; i < _Container.size() - 1; i++)
    {
        bool is_swapped = false;
        for (size_t j = 0; j < _Container.size() - i - 1; j++)
        {
            _Iterations++;
            if (_Container[j] > _Container[j + 1])
            {
                _Compares++;
                swap(_Container[j], _Container[j + 1]);
                is_swapped = true;
            }
        }

        if (!is_swapped)
            break;
    }
}

int main()
{
    std::random_device seed;
    std::mt19937 generator(seed());
    const std::uniform_int_distribution<> random_result(kLeftNumRange, kRightNumRange);

    vector<int> test(kFirstSize);
    vector<int> test_s(kSecondSize);
    vector<int> test1(kFirstSize);
    vector<int> test1_s(kSecondSize);
    vector<int> test2(kFirstSize);
    vector<int> test2_s(kSecondSize);

    for (size_t i = 0; i < kFirstSize; i++)
    {
        test[i] = random_result(generator);
        test1[i] = random_result(generator);
        test2[i] = random_result(generator);
    }
    for (size_t i = 0; i < kSecondSize; i++)
    {
        test_s[i] = random_result(generator);
        test1_s[i] = random_result(generator);
        test2_s[i] = random_result(generator);
    }

    //..................... Bubble Sort

    cout << "######################################### BUBBLE SORT #########################################" << endl;

    size_t iterations = 0, compares = 0;

    // 100
    cout << "100 numbers BEFORE Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test[it] << " ";
    }
    bubble_sort(test, iterations, compares);

    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << endl
        << "100 numbers AFTER Sort : " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test[it] << " ";
    }
    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << "RESULTS: Iterations = " << iterations << " | Compares = " << compares << endl << endl;

    // 1000
    iterations = compares = 0;
    cout << "1000 numbers BEFORE Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test_s.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test_s[it] << " ";
    }
    bubble_sort(test_s, iterations, compares);

    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << endl
        << "1000 numbers AFTER Sort : " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test_s.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test_s[it] << " ";
    }
    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << "RESULTS: Iterations = " << iterations << " | Compares = " << compares << endl << endl;

    //..................... Heap Sort

    iterations = compares = 0;
    // 100
    cout << "########################################## HEAP SORT ##########################################" << endl;
    cout << endl
        << "100 numbers BEFORE Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test1.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test1[it] << " ";
    }
    heap_sort(test1, test1.size(), iterations, compares);

    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << endl
        << "100 numbers AFTER Sort : " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test1.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test1[it] << " ";
    }
    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << "RESULTS: Iterations = " << iterations << " | Compares = " << compares << endl << endl;

    iterations = compares = 0;

    // 1000
    cout << endl
        << "1000 numbers BEFORE Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test1_s.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test1_s[it] << " ";
    }
    heap_sort(test1_s, test1_s.size(), iterations, compares);

    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << endl
        << "1000 numbers AFTER Sort : " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test1_s.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test1_s[it] << " ";
    }
    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << "RESULTS: Iterations = " << iterations << " | Compares = " << compares << endl << endl;

    //..................... Quick Sort

    iterations = compares = 0;

    // 100
    cout << "########################################## QUICK SORT #########################################" << endl;
    cout << endl
        << "100 numbers BEFORE Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test2.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test2[it] << " ";
    }
    quick_sort(test2, 0, test2.size() - 1, iterations, compares);

    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << endl
        << "100 numbers AFTER Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test2.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test2[it] << " ";
    }
    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << "RESULTS: Iterations = " << iterations << " | Compares = " << compares << endl << endl;

    iterations = compares = 0;
    // 1000

    cout << endl
        << "1000 numbers BEFORE Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test2_s.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test2_s[it] << " ";
    }
    quick_sort(test2_s, 0, test2_s.size() - 1, iterations, compares);

    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << endl
        << "1000 numbers AFTER Sort: " << endl
        << "----------------------------------------------------------------------------------------------";
    for (size_t it = 0; it < test2_s.size(); it++)
    {
        if (it % kSpacingSize == 0)
            cout << endl;
        cout << setw(4) << test2_s[it] << " ";
    }
    cout << endl
        << "----------------------------------------------------------------------------------------------" << endl;
    cout << "RESULTS: Iterations = " << iterations << " | Compares = " << compares << endl << endl;
    return 0;
}