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
Code:
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])
Dans cet algorithme, on remarque deux choses
- La fonction échanger qui permettra d'échanger deux entiers.
- 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
Code:
#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; }
Code n°1:
Code:
void echanger(int a, int b){ int temp = b; b = a; a = b; }
Code:
x=12 et y=8
Essayons en revoyant les bases du C co
Code n°2:
Code:
void echanger(int *a, int *b){ int temp = *b; *b = *a; *a = temp; }
Code:
#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; }
Code:
x=8 et y=12
Vous inquiétez pas, il y a une autre solution, regardez ce code,
Code n°3:
Code:
void echanger(int &a, int &b){ int temp = b; b = a; a = temp; }
On va tout de même faire le test
Code:
#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; }
Code:
x=8 et y=12
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,
Code:
void Tri_bulles(vector<int> &T);
Code:
#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; }