/* Учебная практика 2019
 * Байдаров Егор БПИ184
 * Среда рaзработки: CLION
 * Сделано: 7 видов сортировок для 4 видов массивов, подсчет операций и вывод в файл
 * Не сделано: -
 */

#include <iostream>
#include <fstream>
#include <random>
#include <cmath>
#include <string>
#include <map>
#include <functional>

using namespace std;
static long long counter = 0;

// своп двух значений
void swap(int& a, int& b)
{
    int c = a;
    a = b;
    b = c;
    counter += 3; //3 присваивания
}

//поиск максимального эл-та в массиве
int maxArr(int* array, int size)
{
    int max = array[0];
    counter += 2;
    counter += 2;
    for (int i = 1; i < size; i++)
    {
        counter += 2;
        if (array[i] > max)
        {
            max = array[i];
            counter += 2;
        }
        counter += 3;
    }
    return max;

}

void countSort(int* array, int size)
{
    int* output = new int[size];
    counter = 1;
    int max = maxArr(array, size);
    counter += 1;
    int* count = new int[max + 1]; // создание массива из max + 1 элементов
    counter += 2;
    counter += 3;
    for (int i = 0; i < max + 1; i++)
    {
        counter += 2;
        count[i] = 0;// инициализация
        counter += 4;
    }
    counter += 2;
    for (int i = 0; i < size; ++i)
    {
        counter += 4;
        ++count[array[i]];     // подсчет элементов
        counter += 3;
    }
    counter += 3;
    for (int i = 1; i < max + 1; ++i)
    {
        counter += 5;
        count[i] += count[i - 1];
        counter += 4;
    }// поиск комулятивных частот
    counter += 3;
    for (int i = size - 1; i > -1; i--)
    {
        int a = array[i];
        output[count[a] - 1] = a;
        count[a]--; //уменьшение числа одинаковых элементов
        counter += 11;
    }
    counter += 2;
    delete[] count;
    delete[] output;
}

static void countSortR(int* arr, int n, int exp)
{
    counter += 2;
    int* output = new int[n]; // массив результатов
    int i;
    int* count = new int[256]; //массив для подсчета вхождений различных елементов
    counter += 2;
    for (int i = 0; i < 256; i++)
    {
        counter += 2;
        count[i] = 0; // его инициализация
        counter += 3;
    }
    counter += 2;
    for (i = 0; i < n; i++)
    {
        counter += 6;
        count[(arr[i] / exp) % 256]++;// подсчет элементов
        counter += 3;
    }
    counter += 2;
    for (i = 1; i < 256; i++)
    {
        counter += 5;
        count[i] += count[i - 1]; // получение коммулятивных частот чисел
        counter += 3;
    }
    counter += 3;
    for (i = n - 1; i >= 0; i--)
    {
        counter += 14;
        output[count[(arr[i] / exp) % 256] - 1] = arr[i];
        count[(arr[i] / exp) % 256]--;// уменьшение числа одинаковых эл-ов
        counter += 3;
    }

    delete[] count;
    delete[] output;

}

void radixSort(int arr[], int n)
{
    counter = 1;
    int m = maxArr(arr, n); // поиск максимального
    counter += 3;
    for (int exp = 1; m / exp > 0; exp *= 256) //что-то неведанное
    {
        countSortR(arr, n, exp);
        counter += 4;
    }
}

void bubbleIver1(int* arr, int len)
{
    counter = 2;
    int i = 0;
    bool fl = true; // флаг для цицла
    counter += 1;
    while (fl == true)
    { // пока замены есть цикл
        fl = false;

        counter++;// 1 присваивание
        counter += 4;// 1 сравнение перед попаданием в цикл, 1 инициаизация
        for (int j = 0; j < len - i - 1; ++j)
        {
            counter += 4;
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]); // pfvtyf lde[ 'ktvtynjd
                fl = true;
                counter += 4;// 1 присваивание, 2 взятия эл массива
            }
            counter += 5;//2 взятия эл массива, 1 сравнение
        }
        ++i;
        counter += 3;// 1 инкремент
    }
}

void bubble(int* arr, int n)
{ // простая сортировка пузырьком
    counter = 3; // инициализация и сравнение
    for (int j = n - 1; j > 0; --j)
    {
        counter += 2; // инициализация и сравнение
        for (int i = 0; i < j; ++i)
        {
            counter += 4;
            if (arr[i + 1] < arr[i])
            {
                counter += 3;//
                swap(arr[i], arr[i + 1]);
            }
            counter += 3; //сравнение инкремент
        }
        counter += 3; //сравнение инкремент
    }
}

void bubbleIver12(int* array, int N)
{
    counter = 1;
    int t = N;
    counter += 1;
    while (t != 0)
    { // пока замены есть цикл
        int bound = t;
        counter += 2;
        t = 0;
        counter += 2;
        for (int i = 1; i < bound; ++i)
        { // проход по сассиву до границы
            counter += 4;
            if (array[i] < array[i - 1])
            {

                swap(array[i], array[i - 1]); // замены двух элементоа
                t = i;
                counter += 4;
            }
            counter += 3;
        }
        counter += 1;
    }
}

void simpleInsert(int* arr, int len)
{ // простые вставки
    counter = 2;
    for (int i = 1; i < len; i++)
    {
        if (i > 0)
            counter += 7;
        else
            counter += 2;
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--)
        { // сдвиг меньшего элемента влево
            counter += 3;
            swap(arr[j - 1], arr[j]);
            if (j - 1 > 0)
                counter += 8;
            else
                counter += 3;
        }
    }
}

void binaryInsert(int* arr, int n)
{ // вставки с бин поиском
    counter = 2;
    for (int i = 0; i < n; ++i)
    {
        counter += 5;
        int left = 0, right = i;
        int temp = arr[i];
        while (left < right)
        { //бинарный поиск
            counter += 6;
            int mid = left + (right - left) / 2;
            if (temp < arr[mid])
            {
                right = mid;
                counter++;
            } else
            {
                left = mid + 1;
                counter += 2;
            }
            counter++;
        }
        counter += 3;
        for (int j = i; j >= left + 1; --j)
        { //сдвиг влево меньшего элемента
            counter += 8;
            arr[j] = arr[j - 1];
        }
        counter += 5;
        arr[left] = temp;
    }
}

// генерация массива числами 0 -9
void randomRange0To9(int* arr, int len)
{
    srand(0);
    for (int i = 0; i < len; ++i)
        arr[i] = rand() % 10;
}

// генерация массива числами 0 -10000
void randomRange0To10000(int* arr, int len)
{
    srand(0);
    for (int i = 0; i < len; ++i)
        arr[i] = rand() % 10001;
}

// генерация почти отсортированного массива
void almostSorted(int* arr, int len)
{
    srand(0);
    for (int i = 0; i < len; ++i)
        arr[i] = i;
    for (int i = 1; i < 10; ++i)
        swap(arr[len - i * 100], arr[len - i * 10]);
}

//генерация обратно сортированного массива
void sortedFrom10000To1(int* arr, int len)
{
    srand(0);
    for (int i = len; i > 0; --i)
        arr[len - i] = i;
}


int main()
{
//    ofstream fout("output.csv");
//
//    //заголовок таблицы
//    string header1 = "ELEMENTS COUNT; bubble - randomRange0To9; bubble - randomRange0To10000; bubble - almostSorted; bubble - sortedFrom10000To1;"
//                     "bubbleIver1 - randomRange0To9; bubbleIver1- randomRange0To10000; bubbleIver1- almostSorted; bubbleIver1- sortedFrom10000To1;"
//                     "bubbleIver12 - randomRange0To9;bubbleIver12 - randomRange0To10000; bubbleIver12- almostSorted; bubbleIver12- sortedFrom10000To1;"
//                     "simpleInsert - randomRange0To9; simpleInsert- randomRange0To10000; simpleInsert- almostSorted; simpleInsert- sortedFrom10000To1;"
//                     "binaryInsert - randomRange0To9; binaryInsert- randomRange0To10000; binaryInsert- almostSorted; binaryInsert- sortedFrom10000To1;"
//                     "countSort - randomRange0To9; countSort- randomRange0To10000; countSort- almostSorted; countSort - sortedFrom10000To1;"
//                     " radixSort - randomRange0To9; radixSort- randomRange0To10000;  radixSort - almostSorted;  radixSort- sortedFrom10000To1;";
//    fout << header1 << endl;
//
//    // массив функций сортировки
//    void (*sort[7])(int* arr, int len) =
//            {
//                    bubble, bubbleIver1, bubbleIver12, simpleInsert, binaryInsert, countSort, radixSort
//            };
//    // массив функций генерации
//    void (*generate[4])(int* arr, int len) =
//            {
//                    randomRange0To9,randomRange0To10000, almostSorted,sortedFrom10000To1
//            };
//
//    for (int i = 1000; i < 8001; i += 1000)
//    {
//        fout << i << ';';
//        for (int j = 0; j < 7; ++j)
//        {
//            for (int k = 0; k < 4; ++k)
//            {
//                int* arr = new int[i];
//                generate[k](arr, i);
//                sort[j](arr, i);
//                fout << counter << ';';// запись результата подсчета
//                delete[] arr;
//
//            }
//
//        }
//        fout << endl;
//
//    }
//    fout.close();
    fstream data("data.txt");
    double temp = 0;
    data >> temp;
    map<double, int> nums;
    nums.insert({temp, 1});
    do
    {
        data >> temp;
        if (nums.find(temp) == nums.end())
            nums.insert({temp, 1});
        else
            nums.find(temp)->second++;
    } while (!data.eof());
    double step = 3.325;
    int sum = 0;
    auto it = nums.begin();
    map<string, int> res;
    double start = it->first;
    for (int i = 0; i < 8; ++i)
    {
        res.insert({to_string(start) + " - " + to_string(start + step), 0});
        while (it->first < start + step)
        {
            res.find(to_string(start) + " - " + to_string(start + step))->second+=it->second;
            it++;
        }
        start = start + step;
    }
    for(const pair<string, int>& pair : res)
    {
        cout << pair.first << " & " << pair.second << " & " << double(pair.second) * 100 /197 << R"(\\ \hline)" << endl;
    }
    double exp = 0;
    for(const pair< double, int>& iter : nums)
    {
        exp += iter.first * iter.second;
    }
    exp = exp /197;
    double disp = 0;
    int i = 0;
    cout << endl << exp << endl;
    for(const pair< double, int>& iter : nums)
    {
        if(iter.first == 0)
            return 1;
        ++i;
        disp += (iter.first - exp) * (iter.first - exp) * iter.second;
    }
    disp = disp/197;
    cout << endl << disp << endl << "   " << i;
    fstream data2("data.txt");
    vector<double> vec;
    do
    {
        double temp = 0;
        data2 >> temp;
        vec.push_back(temp);
    }while(!data2.eof());
    disp = 0;
    i = 0;
    for(const double& iter : vec)
    {
        if(iter == 0)
            break;
        ++i;
        disp += (iter - exp) * (iter - exp);
        //cout << iter << endl;
    }
    disp = disp/197;
    cout << endl << disp << endl << "  " << i;
    return 0;
}