#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <stdio.h>
#include <conio.h>
#include <algorithm>
#include <ctime>
#define jump 100000
#define qty 10

using namespace std;

void display(int size, int *nrs)
{
    system("cls");
    for (int i = 0; i < size; i++)
    {
        cout << *nrs << " ";
        nrs++;
    }
    cout << endl;
    system("pause");
    return;
}

void IS(int size, int *nrs) //Insertion sort
{
    return;
}

void SS(int size, int *nrs) //Selection sort
{
    return;
}

void BS(int size, int *nrs) //Bubble sort xD
{
    for (int i = 0; i < size; i++)
    {
        if (size > 50000) break;
        for (int j = 0; j < (size - i - 1); j++)
        {
            if (nrs[j] > nrs[j + 1]) swap(nrs[j], nrs[j + 1]);
        }
    }
    return;
}

void HS(int size, int *nrs) //Heap sort
{
    return;
}

void QS(int size, int *nrs) //Quick sort
{
    return;
}

void MS(int size, int *nrs) //Merge sort
{
    return;
}

void ShS(int size, int *nrs) //Shell sort
{
    return;
}

void CS(int size, int *nrs) //Counting sort
{
    int* hold = new int [size];
    int* nrs_sorted = new int [size];

    for(int i = 0; i < size; ++i) hold[i] = 0;

    for(int i = 0; i < size; ++i) ++hold[nrs[i]];

    for(int i = 1; i < size; ++i) hold[i] += hold[i-1];

    for(int i = size - 1; i >= 0; --i) nrs_sorted[--hold[nrs[i]]] = nrs[i];

    delete [] hold;
    delete [] nrs_sorted;

    return;
}

void to_file()
{
    ex1 << "CHUJ";
}

void exercise1()
{
    system("pause");
    system("cls");

    ofstream ex1; ex1.open("Zadanie_1.txt");
    ex1 << left << setw(15) << "SoRtInG" << "BS:    " << "HS:   " << "CS:   " << "ShS:" << endl << endl;

    for (int i = jump; i < (qty * jump) + 1; i += jump)
    {
        cout << left << setw(15) << i;

        int* nrs = new int [i];

        for (int j = 0; j < i; j++) nrs[j] = rand() % i;

        clock_t start, stop;
        double time;

        start = clock();
        BS(i, nrs);
        stop = clock();
        cout << "   " << (double (stop - start)) / CLOCKS_PER_SEC << "  ";
        ex1 << left << setw(15) << i << (double (stop - start)) / CLOCKS_PER_SEC;

        start = clock();
        HS(i, nrs);
        stop = clock();
        cout << "   " << (double (stop - start)) / CLOCKS_PER_SEC << "  ";
        ex1 << "    " << (double (stop - start)) / CLOCKS_PER_SEC;

        start = clock();
        CS(i, nrs);
        stop = clock();
        cout << "   " << (double (stop - start)) / CLOCKS_PER_SEC << "  ";
        ex1 << "    " << (double (stop - start)) / CLOCKS_PER_SEC;

        start = clock();
        ShS(i, nrs);
        stop = clock();
        cout << "   " << (double (stop - start)) / CLOCKS_PER_SEC << endl;
        ex1 << "    " << (double (stop - start)) / CLOCKS_PER_SEC << endl;

        delete [] nrs;
    }

    ex1.close();
    ex1.clear();
    return;
}

void exercise2()
{
    return;
}

int main()
{
    exercise1();
    //exercise2();
    return 0;
}