Fonctions C

La fonction ''rand()'' retourne une valeur alérateoire entre 0 et RAND_MAX.

Pour calculer une valeur aléatoire comprise entre theMinValue et theMaxValue, le code suivant peut-être utilisé :

#include<cstdlib>
 
std::srand(std::time(nullptr));
    // Initialise la racine du générateur de 
    // nombre aléatoire avec la valeur temporelle 
    // actuelle.
int width = theMaxValue - theMinValue;
int randomValue = theMinValue + (std::rand() % width);
    // Retourne une valeur entre theMaxValue et theMinValue

Approche C++

A partir de C++, la bibliothèque STL propose des classes implantant différents générateurs de nombres aléatoires et proposant différentes distributions. Pour les besoins de la question, nous nous intéressons à la classe ''std::uniform_int_distribution'' qui génère des séquences de valeurs pseudo-aléatoires selon une loi de distribution dite uniforme.

#include <random>
#include <iostream>
 
std::random_device rd;  
    // Générateur de nombres alératoire qui est utilisé 
    // comme racine d'une séquence de nombres aléatoires.
std::minstd_rand gen(rd()); 
    // Générateur générant des nombres aléatoires initialisées 
    // par une valeur tirée au hasard par le générateur rd. 
std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
    // Crée une distribution qui prend une valeur générée par un
    // générateur aléatoire et retournant une valeur uniformément 
    // distribuée entre theMinValue et theMaxValue.
 
int randomValue = distribution(generator);
    // Une valeur générée entre theMinValue et theMaxValue de 
    // manière équiprobable.

Nous proposons plusieurs solutions au problème. Première approche, nous supprimons l'ensemble des valeurs dans le vecteur theVector en effectuant un appel à la fonction clear de l'object std::vector et nous ajoutons à la fin du vecteur, un par un les valeurs aléatoires que nous tirons en appelant la fonction push_back. Suivez le lien pour plus d'informations relativement aux méthodes de la classe ''std::vector''.

#include "../include/simple_sort.hpp"
#include<random>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.clear();
        for(;
            theNumberOfValues > 0;
            theNumberOfValues --)
        {
            theVector.push_back(
                distribution(gen));
        }
    }
}

Une autre solution équivalente consiste à redimensionner le tableau dynamique std::vector à la taille spécifiée par le paramètre theNumberOfValues, l'appel à la méthode resize de std::vector va initialiser exactement theNumberOfValues avec la valeur par défaut. Il est possible ensuite d'affecter à chaque entrée du tableau une valeur aléatoire avec l'opérateur d'accès indexé [].

#include "../include/simple_sort.hpp"
#include<random>
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.resize(theNumberOfValues);
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                distribution(gen));
        }
    }
}

Cependant, nous pouvons constater que nous procédons systématiquement à l'initialisation du générateur de nombre pseudo-aléatoire lorsque nous appelons la fonction std::populate_with_randoms, ce qui n'est pas souhaitable en terme d'efficacité ou au contraire de qualité de la génération des séquence de nombres.

Pour ce faire, nous avons deux approches, soit nous déclarons le générateur comme une variable globale.

#include<random>
 
std::random_device rd;
std::minstd_rand gen(rd());
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.resize(theNumberOfValues);
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                distribution(gen));
        }
    }
}

soit au contraire, nous définissons le générateur de nombre pseudo-aléatoire comme étant une variable statique de fonction, ceci signifie que la variable est partagée entre tous les appels de la fonction, il s'agit d'une variable globale qui n'est visible que par la fonction et qui est initialisée lors du premier appel à la fonction.

#include "simple_sort.hpp"
#include<random>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        static std::random_device rd;        // Variables statiques, initialisées uniquement
        static std::minstd_rand gen(rd());   // lors du premier appel de la fonction et persistant
                                             // entre deux appels de fonctions.
 
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.resize(theNumberOfValues);
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                distribution(gen));
        }
    }
}

Si vous utilisez en lieu et place des classes std::random_device, std::minstd_rand et std::uniform_int_distribution<> les appels aux fonctions std::srand et std::rand, nous obtenons le code suivant :

#include "simple_sort.hpp"
#include<cstdlib>
#include<ctime>

namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::srand(std::time(nullptr)); 
            // Initialisation de la racine, du générateur de nombre aléatoir, 
            // peut-être déplacé au début 
            // du programme comme étant la première instruction 
            // dans la fonction ''main''
        theVector.resize(theNumberOfValues);
        int width = theMaxValue - theMinValue;
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                theMinValue + (std::rand() % width);
        }
    }
}

Votre fonction ressemblera à la fonction suivante :

#include "simple_sort.hpp"
#include<iostream>
 
namespace monomorphic
{
    void print_vector(const std::vector<int>& anArray)
    {
        int length = anArray.size();
        std::cout << "[";
        for(int index = 0; index < length - 1; index ++)
            std::cout << anArray[index] << ", ";
        std::cout << anArray[length - 1] << "]" << std::endl;
    }
}

Il s'agit d'un tri par insertion. Nous pouvons envisager d'implanter d'autre tri, comme un tri par bulles par exemple.

Nous avons dans le code précédent explicité l'opération d'échange entre la case i et la case j du tableau. Nous pouvons aussi utiliser la fonction ''std::swap'' qui est définie dans la STL dans le fichier d'entête ''algorithm''. Dans ce cas, le code se simplifie en :

void simple_sort(std::vector<int>& theValues)
{
    for (int i = 0; i<theValues.size(); i++)
    {
        for (int j = i + 1; j< theValues.size(); j++)
        {
            std::swap(theValues[i], theValues[j]);
        }
    }
}

Après cet ajout, votre fichier simple_sort.cpp devrait ressembler au fichier suivant :

#include "simple_sort.hpp"
 
#include<algorithm>
#include<random>
#include<iostream>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.clear();
        for(;
            theNumberOfValues > 0;
            theNumberOfValues --)
        {
            theVector.push_back(
                distribution(gen));
        }
    }
    void print_vector(const std::vector<int>& anArray)
    {
        int length = anArray.size();
        std::cout << "[";
        for(int index = 0; index < length - 1; index ++)
            std::cout << anArray[index] << ", ";
        std::cout << anArray[length - 1] << "]" << std::endl;
    }
 
    void simple_sort(std::vector<int>& theValues)
    {
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(theValues[i] > theValues[j])
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
}

Il suffit d'écrire dans votre fnction main le code suivant :

#include <iostream>
#include"include/simple_sort.hpp"
#include<string>
 
using namespace std;
 
int main()
{
    {
        using namespace monomorphic;
 
        std::vector<int> values;
        populate_with_randoms(values, 10, 1, 10);
        print_vector(values);
        simple_sort(values);
        print_vector(values);
    }

Nous avons dans le code précédent défini une portée débutant par { using namespace monomorphic;. Ceci indique que dans cette portée qui se termine avec le } correspondant nous importons l'ensemble des fonctions contenues dans l'espace de nom monomorphic. Cette importation permet de ne pas avoir à écrire le préfix monomorphic:: devant les fonctions populate_with_randoms, print_vector et simple_sort.