//
//  main.cpp
//  tris
//
//  Created by Dylan BUTELLE on 06/04/2020.
//  Copyright © 2020 Dylan BUTELLE. All rights reserved.
//
#include <iostream>
#include <array>
#include <time.h>
#include <cstdlib>
#include <iomanip>
using namespace std;
const int N=10;
void init3Tab(array<int,N> & Talea,array<int,N> &Tdec,array<int,N> &Ttrie)
{
    int j=N-1;
    for(int i=0;i<N;i++){
        Talea[i]=rand()%N;
        Tdec[i]=j;
        Ttrie[i]=i;
        j--;
        }

}

void triSelection (array<int, 50> & tabI, int taille, long & cpt) {
    int ind, position, maximum, i, tmp;
    cpt=0;
    for (ind=taille; ind>=1;ind--) { //E1
        position = 0; //E2
    for (i=1;i<=ind;i++) { //E3
        if (tabI[position] < tabI[i]) { //E4
            cpt++;
            position = i; //E5
        }
    }
    if (position != ind) { //E6
        tmp = tabI[position]; //E7
        tabI[position] = tabI[ind]; //E8
        tabI[ind] = tmp; //E9
        }
    }
}
void triInsertion (array<int, 50> &tabI, long & cpt) {
    int indice_elt, position, elt;
    cpt=0;
        for (indice_elt=1;indice_elt<=49;indice_elt++) { //E1
            elt = tabI[indice_elt];
            position = indice_elt;
        while (position > 0 && tabI[position-1] > elt) { //E2
            tabI[position] = tabI[position-1]; //E3
            cpt++;
            position=position-1;
        }
            tabI[position] = elt;
        }
}
void fusion (array<int, 50> &tabI, int debut, int milieu, int fin,long & cpt) {
    array<int, 50> tmp;
    int cptG, cptD,i=0,j;
    cptG = debut;
    cptD = milieu+1;
        while ((cptG<=milieu) && (cptD<=fin)) { //E1 : 2 tableaux non vides
                cpt++;
            if (tabI[cptG] < tabI[cptD]) {
                tmp[i] = tabI[cptG];
                cptG = cptG+1;
                }
                    else {
                    tmp[i] = tabI[cptD];
                    cptD = cptD+1;
            }
                i = i+1;
        } //un des 2 tableaux (ou les 2) est vide
        while (cptD <= fin) { //E2 : tableau gauche vide, on complete avec tableau droit trie
            tmp[i] = tabI[cptD];
            cptD = cptD+1;
            i = i+1;
        }
            while (cptG <= milieu) { //E3 : tableau droit vide, on complete avec tableau gauche trie
                tmp[i] = tabI[cptG];
                cptG = cptG+1;
                i = i+1;
            }
        for (j=0;j<=i-1;j++) { //E4 : recopie du tableau temporaire dans
            tabI[debut+j] = tmp[j] ;
        }
    }
void tri_fusion (array<int, 50> &tabI, int debut, int fin,long &cpt) {
    int milieu;
        if (debut < fin) {
            milieu = (fin+debut)/2;
            tri_fusion(tabI, debut, milieu,cpt);
            tri_fusion(tabI, milieu+1, fin,cpt);
            fusion(tabI, debut, milieu, fin,cpt);
        }
    }


int main()
{
    srand(time(NULL));
    array<int,N> Talea;
    array<int,N> Tdec;
    array<int,N> Ttrie;
    long cpt;
    double tps;
    init3Tab(Talea,Tdec,Ttrie);
//affichage cadre du tableau
cout << "\t\t\t" << setw(14) << " selection " << "\t" << setw(15) << "insertion "
<< "\t" << setw(16) << "fusion "<< endl;
cout << "\t\t\t" << setw(14) << " cpt tps " << "\t" << setw(15) << " cpt tps"
<< "\t" << setw(16) << " cpt tps" << endl;
///////////////////// 3 tris sur Talea
cout << "Tableau aleatoire ";
//appel tri selection et calcul de cpt_etape + calcul du temps d'exécution tps
cout << setw(4) << "|" << setw(7) << cpt_etape << " |" << setw(7) << tps;
//appel tri insertion et calcul de cpt_etape + calcul du temps d'exécution tps
cout << setw(2) << "|" << setw(7) << cpt_etape << " |" << setw(7) << tps;
//appel tri fusion et calcul de cpt_etape + calcul du temps d'exécution tps
cout << setw(2) << "|" << setw(7) << cpt_etape << " |" << setw(7) << tps << endl;
return 0;
}