Dans un fichier texte (= dans un flux), un mot est une suite de caractères sans caractère d’espacement (espace, tabulation, passage à la ligne suivante ‘\n’).

Ecrire la fonction ExtractionsMots() qui, dans une boucle, extrait (opérateur >>) au clavier (ou sur un fichier redirigé sur l’entrée standard cin) tous les mots et les affiche à l’écran à raison d’un par ligne. La boucle se termine lorsque l’extraction échoue (fail()).

Faire plusieurs essais, en saisissant un mot par ligne, plusieurs mots sur la même ligne, en utilisant les tabulations, en saisissant des lignes vierges ou seulement composées de caractères d’espacement.

Vous devez constater que :

1. n’importe quel caractère (sauf espacement) peut être considéré comme un mot (un ‘.’ seul par exemple),
2. tous les caractères d’espacement avant un mot sont ignorés,
3. la seule façon de terminer le programme est de taper le caractère “fin-de-fichier” (Ctrl+D). La condition d’arrêt peut donc aussi utiliser le prédicat eof()

Ecrire la fonction extractionsCars() qui, dans une boucle, extrait (opérateur >>) au clavier (ou sur un fichier redirigé sur l’entrée standard cin) tous les caractères et les affiche à l’écran à raison d’un par ligne. La boucle se termine lorsque l’extraction échoue (fail()).

Faire plusieurs essais, en saisissant un ou plusieurs caractères par ligne, séparés ou non par des caractères d’espacement, en saisissant des lignes vierges ou seulement composées de caractères d’espacement.

Vous devez constater que :

1. n’importe quel caractère éditable (sauf espacement) est extrait,
2. tous les caractères d’espacement sont ignorés,
3. la seule façon de terminer le programme est de taper le caractère “fin-de-fichier” (Ctrl+D). La condition d’arrêt peut donc aussi utiliser le prédicat eof() .

Un entier est une suite de caractères numériques (digits) éventuellement précédé d’un signe + ou -. Pour qu’un entier soit valide, il faut que la chaîne de caractères qui le représente soit compatible avec son type :

1. un entier non signé ne peut être précédé du signe -,
2. la valeur de la chaîne ne peut excéder la valeur maximale du type correspondant (32767 pour un short, 65535 pour un unsigned, etc.

Ecrire la fonction extractionsEntiers() qui, dans une boucle, extrait (opérateur >>) au clavier (ou sur un fichier redirigé sur l’entrée standard cin) tous les entiers et les affiche à l’écran à raison d’un par ligne. La boucle se termine lorsque l’extraction échoue (fail()).

Faire plusieurs essais, en saisissant un ou plusieurs entiers par ligne, séparés ou non par des caractères d’espacement, en saisissant des lignes vierges ou seulement composées de caractères d’espacement.

Vous devez constater que :

1. n’importe quel entier valide est extrait,
2. tous les caractères d’espacement sont ignorés,
3. le programme se termine au premier échec d’extraction. Le caractère “fin-de-fichier” (Ctrl+D) permet aussi de terminer la saisie. La condition d’arrêt ne doit pas utiliser le prédicat eof(), sauf si aucune erreur de saisie n’est à craindre (ce qui est plutôt rare !)

Un nombre réel peut être représenté sous deux formes dites virgule fixe ou notation scientifique (ou virgule flottante).

1. un nombre en virgule fixe est composé d’au maximum quatre parties contiguës (sans espace ou séparateur quelconque) :
   1. son signe : ‘+’ ou ‘-‘. S’il est absent, le nombre est considéré comme positif.
   2. sa partie entière, toujours exprimée en base 10,
   3. le caractère point décimal ‘.’ car nous sommes dans le système anglo-saxon !
   4. sa partie décimale, elle aussi toujours exprimée en base 10,

   Si le point décimal est présent, il doit obligatoirement être précédé ou suivi d’au moins un digit décimal.

2. un nombre en notation scientifique est composé de trois parties obligatoires :
   1. un nombre réel en virgule fixe, exprimé en base 10, signé ou non,
   2. le caractère ‘e’ ou ‘E’,
   3. un nombre entier exprimé en base 10, signé ou non, qui représente la puissance de 10 par laquelle il faut multiplier la première partie pour obtenir la valeur réelle.

      De plus, pour que la chaîne représentant un nombre réel soit valide, il faut que la valeur soit compatible avec le type correspondant (float ou double).

Ecrire la fonction extractionsReels() qui, dans une boucle, extrait (opérateur >>) au clavier (ou sur un fichier redirigé sur l’entrée standard cin) tous les réels et les affiche à l’écran à raison d’un par ligne. La boucle se termine lorsque l’extraction échoue (fail()).

Faire plusieurs essais, en saisissant un ou plusieurs réels par ligne, séparés ou non par des caractères d’espacement, en saisissant des lignes vierges ou seulement composées de caractères d’espacement.

Vous devez constater que :

1. n’importe quel réel valide est extrait,
2. tous les caractères d’espacement sont ignorés,
3. le programme se termine au premier échec d’extraction (voir les indications ci-dessus). Le caractère “fin-de-fichier” (Ctrl+D) permet aussi de terminer la saisie.

Les réels suivants sont valides :

123
123.45
-12e12
-12.e-12
+12.23
-.23
1234567890

La dernière valeur est valide mais tronquée : 1.23457e+09.

Les réels suivants sont invalides et terminent le programme :

-.e12
1e123456789
-e12

Ecrivez la procédure triSelection () de signature

void triSelection (vector<unsigned> & vUint);

Cette procédure trie le vecteur en paramètre selon la méthode du tri par sélection / échange (cf. R1.01 – Algo8 – eox2).

Afin d’initialiser votre vecteur, ajouter ces lignes dans le main () :

#include <cstdlib>
#include <ctime>
...
srand (time(NULL));
vector<unsigned> vUInt (XXX);

for (auto & val : vUInt)
     val = rand () % (vUInt.size() * 10);

Pour finir, écrivez la fonction testVecteurTrie () de signature

void testVecteurTrie (const vector<unsigned> & vUint);

Cette fonction doit tester si le vecteur qui lui est passé en paramètre est trié. Cette vérification doit de faire à l’aide de la fonction assert ().

NB : pensez à mettre un message à la fin de votre fonction testVecteurTrie () pour vous assurer que vous passez tous les tests.

Ecrivez la procédure triInsertion () de signature

void triInsertion (vector<unsigned> & vUint);

Cette procédure trie le vecteur en paramètre selon la méthode du tri par insertion (cf. R1.01 TD8 – eox4).

Utilisez la fonction testVecteurTrie () pour vous assurer que le vecteur est trié.

Ecrivez la procédure triABulles () de signature

void triABulles (vector<unsigned> & vUint);

Cette procédure trie le vecteur en paramètre selon la méthode du tri par insertion (cf. R101 TD8 – eox3).

Utilisez la fonction testVecteurTrie () pour vous assurer que le vecteur est trié.

Ecrivez la procédure triComptage () de signature

void triComptage (vector<unsigned> & vUint);

Cette procédure trie le vecteur en paramètre selon la méthode du tri par insertion (cf. R1.01 TD8 – eox5).

Utilisez la fonction testVecteurTrie () pour vous assurer que le vecteur est trié.

Insérer dans le code suivant vos algorithmes de tri.
Modifier le .pro en ajoutant la ligne LIBS += -pthread

Puis faite divers tests en faisant varier les paramètres d’entrée :

1. la taille des vecteurs;
2. le nombre de vecteurs différents;
3. nombre d’itérations par vecteur;

#include <iostream>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <thread>
#include <cassert>

using namespace std;
typedef vector <vector<double>> CMatrix;

CMatrix Mat;

void selectSort (vector <unsigned> & tab){
    //TODO
}

void insertSort (vector <unsigned> & vUint)
{
//TODO
}

void bubbleSort (vector <unsigned> & vUint)
{
//TODO
}

void countingSort (vector <unsigned> & vUint)
{
//TODO
}

void languageSort (vector<unsigned> & VUint)
{
    sort (VUint.begin(), VUint.end());
}

void initMat (unsigned NbColumns)
{
    Mat.resize(5, vector <double> (NbColumns));
}

//http://stackoverflow.com/questions/2962785/c-using-clock-to-measure-time-in-multi-threaded-programs
void protoGenericSort(void (*mySort) (vector <unsigned> & vUint), const vector <unsigned> & vUint, unsigned NbFois, unsigned PosMat, unsigned VectNum)
{
    for (unsigned i (0); i < NbFois; ++i)
    {
        vector <unsigned> copyVUint (vUint);
        struct timespec start, finish;
        double elapsed;
        clock_gettime(CLOCK_MONOTONIC, &start);
        mySort (copyVUint);
        clock_gettime(CLOCK_MONOTONIC, &finish);
        elapsed = (finish.tv_sec - start.tv_sec);
        elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
        Mat [PosMat][i + NbFois * VectNum] = elapsed;
    }
}

void traiterResultats (const unsigned & nbElemAEnlever)
{
    for (vector <double> & UneLigne : Mat)
    {
        //tri
        sort (UneLigne.begin(), UneLigne.end());
        //suppresion des éléments non significatifs
        UneLigne = vector <double> (UneLigne.begin() + nbElemAEnlever / 2, UneLigne.end() - nbElemAEnlever / 2 );
        //plus petit temps
        double min (UneLigne[0]);
        //plus grand temps
        double max (UneLigne[UneLigne.size()-1]);
        //temps median
        double med (UneLigne[UneLigne.size()/2]);

        //On assigne les valeurs memorisees aux 3 premières cases
        UneLigne[0] = min;
        UneLigne[1] = med;
        UneLigne [2] = max;
    }
    //Affichage
    cout << setw (20) << "Tri" << setw (10) << "Min" << setw (10) << "Med" << setw (10) << "Max" << endl;
    vector<string> VMetode {"Selection", "Insertion", "Bulles", "comptage", "Langage"};
    for (unsigned i (0); i < VMetode.size(); ++i)
        cout << setw (20) << VMetode[i] << setw (10) << setprecision(6) << Mat[i][0] << setw (10) << setprecision(6) << Mat[i][1] << setw (10) << setprecision(6) << Mat[i][2] << endl;

}

int main(int argc, char *argv[])
{
    if (argc != 4)
    {
        cerr << "boulette !\n utilisation : " << argv [0] << " (1) NbElem par vecteur (2) Nb de vecteurs differents (3) Nb itérations par vecteur" << endl;
        return 1;
    }

    unsigned NbElem (stoul(argv[1]));
    unsigned NbVecteurs (stoul(argv[2]));
    unsigned NbFois (stoul(argv[3]));

    srand (time(NULL));
    vector <unsigned> VUInt (NbElem);
    initMat (NbFois * NbVecteurs);


    for (unsigned i (0); i < NbVecteurs; ++i)
    {
        for (auto & Val : VUInt)
            Val = rand () % (VUInt.size() * 10);

        thread th1 (protoGenericSort, selectSort, VUInt, NbFois, 0, i);
        thread th2 (protoGenericSort, insertSort, VUInt, NbFois, 1, i);
        thread th3 (protoGenericSort, bubbleSort, VUInt, NbFois, 2, i);
        thread th4 (protoGenericSort, countingSort, VUInt, NbFois, 3, i);
        thread th5 (protoGenericSort, languageSort, VUInt, NbFois, 4, i);
        th1.join();
        th2.join();
        th3.join();
        th4.join();
        th5.join();
        cout << i << "fini" << endl;
    }

    cout << "Taille des vecteurs : " << NbElem << "\nNb de vecteurs : " << NbVecteurs << "\nNb iterations par vecteur : " << NbFois << endl;
    //On traite les résultats en supprimant 10% des éléments
    traiterResultats (NbFois * NbVecteurs / 10);
    return 0;
}