M1103-TP21 Corrigé

#include 
#include 
#include 
#include 
#include 
#include 
#include 


using namespace std;

typedef vector  CVUint;
typedef vector < vector > CMatrix;

CMatrix Mat;

void SelectSort (CVUint & VUint)
{
    for (unsigned i (0); i < VUint.size(); ++i)
    {
        CVUint::iterator Min (min_element (VUint.begin() + i, VUint.end()));
        swap (VUint[i],VUint [Min - VUint.begin()]);
    }
}

void InsertSort (CVUint & VUint)
{
    for (unsigned i (1); i < VUint.size(); ++i)
    {
        unsigned Val (VUint [i]);
        unsigned j (i);
        for (; j > 0 && VUint[j - 1] > Val; --j)
            VUint[j] = VUint[j - 1];
        VUint[j] = Val;
    }
}

void BubbleSort (CVUint & VUint)
{
    for (unsigned i (VUint.size()); i -- > 0; )
    {
        bool TableauTrie = true;
        for (unsigned j (0); j < i ; ++j)
        {
            if (VUint[j + 1] < VUint[j])
            {
                swap (VUint[j + 1], VUint[j]);
                TableauTrie = false;
            }
        }
        if (TableauTrie) return;
    }
}

void LanguageSort (CVUint & VUint)
{
    sort (VUint.begin(), VUint.end());
}

void InitMat (unsigned NbColumns)
{
    Mat.resize(4, vector  (NbColumns));
}

//http://stackoverflow.com/questions/2962785/c-using-clock-to-measure-time-in-multi-threaded-programs
void protoGenericSort(void (*Sort) (CVUint & VUint), const CVUint & VUint, unsigned NbFois, unsigned PosMat, unsigned VectNum)
{
    for (unsigned i (0); i < NbFois; ++i)
    {
        CVUint CopyVUint (VUint);
        struct timespec start, finish;
        double elapsed;
        clock_gettime(CLOCK_MONOTONIC, &start);
        Sort (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  & UneLigne : Mat)
    {
        //tri
        sort (UneLigne.begin(), UneLigne.end());
        //suppresion des éléments non significatifs
        UneLigne = vector  (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 VMetode {"Selection", "Insertion", "Bulles", "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));
    CVUint 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, LanguageSort, VUInt, NbFois, 3, i);
        th1.join();
        th2.join();
        th3.join();
        th4.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;
}

M1103-TD1 Exercie1 Corrigé

procedure TriSelection (TabInt : in_out tableau_de entier)
debut
pour (i variant_de 0 a taille(TabInt) - 1)
faire
declarer min : entier_naturel;
min <-  i;
pour (j variant_de i + 1 a taille(TabInt) - 1)
faire
si (TabInt[j] < TabInt[min])
min <- j;
fsi
ffaire
si (min ne_vaut_pas i)
PermuterEntier (TabInt[i], TabInt[min]);
fsi
ffaire
fin

M1103-TD1 Exercie2 Corrigé

procedure TriInsertion (TabInt : in_out tableau_de entier)
debut
pour (i variant_de 1 a taille(TabInt) - 1)
faire
declarer x : entier;
x <- TabInt [i];
declarer j : entier_naturel;
j <- i;

tant_que ((j > 0) ET_ALORS (TabInt[j - 1] > x))
faire
TabInt[j] <- TabInt[j - 1];
j <- j - 1;
ffaire

TabInt[j] <- x;
ffaire
fin

M1103-TD1 Exercie3 Corrigé

procedure TriBulles (TabInt : in_out tableau_de entier)
debut
pour (i variant_de taille(TabInt) - 1 a 1 descendant)
faire
pour (j variant_de 0 a i - 1)
faire
si (TabInt[j+1] < TabInt[j])
PermuterEntier (TabInt[j+1], TabInt[j]);
fsi
ffaire
ffaire
fin