C++ - cours n°4 -> Transmission par référence

[fred]

Transmission par référence - Algorithme du tri à bulles

Pré-requis

Les pointeurs en C
Les boucles
Les fonctions
L'objet vector

Problématique

On demande à l'aide d'un tableau d'entiers, de trier ses valeurs dans l'ordre croissant en utilisant un algorithme peu efficace, le tri à bulles.

Présentation de l'algorithme du tri à bulles

tri_à_bulles(Tableau T)
   pour i allant de taille de T - 1 à 1
       pour j allant de 0 à i - 1
           si T[j+1] < T[j]
               échanger(T[j+1], T[j])

Source -> Wikipedia

Dans cet algorithme, on remarque deux choses

1. La fonction échanger qui permettra d'échanger deux entiers.
2. Le tableau T est modifié à la volée

Échanger deux valeurs

On va essayer plusieurs codes, afin de tester si l'échange entre deux entiers fonctionnent

Tout d'abord notre code de test, qui permettra de vérifier à chaque fois la fonction echanger

#include <iostream>

using namespace std;

void echanger(int a, int b);

int main(){

    int x=12, y=8;

    echanger(x, y);

    cout << "x=" << x << " et y=" << y << endl;


    return 0;
}

Commençons par le code le plus intuitif,

Code n°1:

void echanger(int a, int b){

    int temp = b;

    b = a;
    a = b;
}

Résultat,

x=12 et y=8

Ok, donc là clairement, c'est pas ça du tout, on aurait dû avoir x=8 et y=12

Essayons en revoyant les bases du C co

Code n°2:

void echanger(int *a, int *b){

    int temp = *b;

    *b = *a;
    *a = temp;

}

Avec le code test suivant,

#include <iostream>

using namespace std;

void echanger(int *a, int *b);

int main(){

    int x=12, y=8;

    echanger(&x, &y);

    cout << "x=" << x << " et y=" << y << endl;


    return 0;
}

Le résultat est,

x=8 et y=12

eurêka, ça fonctionne, mais beurk, encore se taper les pointeurs comme en C, pfff, j'ai pas fais du C++ pour me retaper du C !!!

Vous inquiétez pas, il y a une autre solution, regardez ce code,

Code n°3:

void echanger(int &a, int &b){

    int temp = b;

    b = a;
    a = temp;

}

plus d'étoiles, juste un passage par référence grâce à l'esperluette (&) qui permet d'avoir l'adresse de nos variables en paramètres et qui permettra de faire l'échange en mémoire.

On va tout de même faire le test

#include <iostream>

using namespace std;

void echanger(int &a, int &b);

int main(){

    int x=12, y=8;

    echanger(x, y);

    cout << "x=" << x << " et y=" << y << endl;


    return 0;
}

Le résultat est celui attendu,

x=8 et y=12

Donc on voit que C++ simplifie largement le problème des pointeurs par ce passage par référence.

Il est donc vital, de comprendre cette fonction qui est la base des transmissions par adresse, car on se rend compte que l'écriture, mais aussi la gestion mémoire sont simplifiés !

Pour ceux qui préfèrent le code n°2, vous embêtez pas, faîtes du C

Création de la fonction de Tri

On passe au chose sérieuse, on a créé notre fonction d'échange simple entre deux entiers, nous n'avons donc plus qu'à terminer le boulot.

On avait dit précédemment, que le tableau était modifié à la volée, ce qui veut dire qu'en paramètre de fonction, notre tableau sera transmis par référence, eh oui !

Le prototype de la fonction sera donc,

void Tri_bulles(vector<int> &T);

Le code de test sera au final le suivant,

#include <iostream>
#include <vector>

using namespace std;

void Tri_bulles(vector<int> &T);
void echanger(int &a, int &b);

int main(){

    vector<int> v;

    v.push_back(5); // insertion de la valeur 5 dans le tableau.
    v.push_back(3);
    v.push_back(9);
    v.push_back(1);
    v.push_back(12);
    v.push_back(0);

    Tri_bulles(v); // le tableau est modifié

    for (int i=0; i<(int)v.size(); i++)
        cout << v.at(i) << endl;


    return 0;
}

void Tri_bulles(vector<int> &T){

    // à compléter
}

void echanger(int &a, int &b){

    int temp = b;

    b = a;
    a = temp;

}

Il ne vous reste plus qu'à compléter le code ci-dessus pour avoir créer votre algorithme dans les règles de l'art.