#include <cstdlib>
#include <iostream>
#include <vector>
#include <random>       // random funktion
#include <algorithm>    // random funktion
#include <functional>   // bind header
#include <chrono>       // zeit

using namespace std;

void controllVector(vector<int>& vV){
    for(int i = 0; i < vV.size()-1 ; i++){
        if(vV[i] > vV[(i+1)]){
            cout << "Fehler" << endl;
            break;
        }
    }
}

void displayVector(vector<int>& v) {            //zeigt den Vector an der Indexstelle "i" an
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << " ";
}

template<typename T>                            //custom template für T

void swap_if(T& a, T& b) {                      //prüft ob b kleiner a ist und vertauscht bei true deren position
    if (b < a) swap(a, b);
}

void selSort(vector<int>& vV, int ui, int oi) { //SelectionSort Function aus der Folie
    int min{0};
    for (int i{ui}; i<oi; ++i) {
    min = i;
    for (int j{i + 1}; j <= oi; ++j)
    if (vV.at(j) < vV.at(min)) min = j;
    swap(vV.at(i), vV.at(min));
     }
}

void insSort_v0(vector<int>& vV, int ui, int oi) { //insSort_v0 aus der Folie
    for (int i{ui + 1}; i <= oi; ++i)
    for (int j{i}; j>ui; --j)
            swap_if(vV.at(j - 1), vV.at(j));
}


void insSort_v2(vector<int>& vV, int ui, int oi) { //insSort_v2 aus der Folie
    int i{0};
    int j{0};
    int tmp{0};
    for (i = oi; ui < i; --i) swap_if(vV.at(i - 1), vV.at(i));
    for (i = ui + 2; i <= oi; ++i) {
        tmp = vV.at(i);
        for (j = i; tmp < vV.at(j - 1); --j)
            vV.at(j) = vV.at(j - 1);
        vV.at(j) = tmp;
    }
}




int main() {

    vector<int> container{};

    using chrono::high_resolution_clock;            //Zeitmess funktion aus der Folie
    using chrono::milliseconds;
    using chrono::duration_cast;
    high_resolution_clock::time_point my_end{};
    high_resolution_clock::time_point my_start{
        high_resolution_clock::now()
    };

    auto ri = bind(uniform_int_distribution<int>{0, 100},   //random number generator
    default_random_engine{});

    for (int i = 0; i < 1000; ++i)                          //erweitert den Vector um den Wert "ri"
        container.push_back(ri());

    displayVector(container);                               //ruft die displayVector Funktion auf

    cout << endl << endl;



    //selSort(container, 0, container.size() - 1);          //verschiedene Sortier Algorithmen
    //insSort_v0(container, 0, container.size() - 1);       //sortiert hier den vector "container"
    insSort_v2(container, 0, container.size() - 1);

    controllVector(container);


    displayVector(container);

    cout << endl << endl;

    my_end = high_resolution_clock::now();
    milliseconds ms{duration_cast<milliseconds>(my_end - my_start)};



    cout << ms.count() << " Millisekunden" << endl;         //gibt hier dann die Zeitmessung aus

    return 0;
}